关于搜索的棘手面试问题

Question

我最近听到一位朋友在接受采访时被问到这个问题.他无法弄清楚,我还没有找到任何有效的解决方案.我希望这里有一位算法师可以向我展示一种新的方法

题:

给定数组A和数字S',提供有效算法(nlogn)以找到数字K,使得如果A中大于K的所有元素都变为K,则结果数组中所有元素的总和将为S' .

例如,给定A: [90,30,100,40,20]和S' = 210,K将60.

Answer 1

用Python编写,即使你不懂语言也应该是可读的:

#!/usr/bin/env python

A = [90, 30, 100, 40, 20]
S = 210
K = 60

A    = sorted(A)
prev = 0
sum  = 0

for index, value in enumerate(A):
    # What do we need to set all subsequent values to to get the desired sum?
    solution = (S - sum) / (len(A) - index)

    # That answer can't be too big or too small.
    if prev < solution <= value:
        print solution

    sum += value
    prev = value

结果:

60

排序为O(n log n),循环为O(n).因此,将算法整体组合为O(n log n).

Answer 2

首先将列表从最小到最大排序,然后查找它的长度.然后开始逐个添加数字.在每个步骤中,还可以找到总和的下限 - 整个列表的总和是多少,如果尚未添加的所有其余数字与当前数字相同.

在某些时候,总和的这个下限将从小于S'变为大于S',并且在那时你可以做一些算术来确定截止应该是什么.例如(C =当前总和,L =总和的下限):

start
[90 30 100 40 20]
sort
[20 30 40 90 100]
start adding up the sum
C1 = 20
L1 = 20 + 4*20 = 100 < 210

C2 = 20 + 30 = 50
L2 = 50 + 3*30 = 140 < 210

C3 = 50 + 40 = 90
L3 = 90 + 2*40 = 170 < 210

C4 = 90 + 90 = 180
L4 = 180 + 1*90 = 270 > 210 //too big!

S' = C3 + K*2
therefore
K = (S'-C3)/2 = 60

Answer 3

这可以通过使用如下的线性时间选择的变化在O(n)时间内进行排序来完成(注意,while循环的迭代的运行时间形成几何系列 - 分区子例程分割数组的范围) ,从低到高,到小于或大于等级元素的元素,运行时间与数组范围的大小成正比):

foo(x, s) {
  sumBelow = 0;
  lower = 0;
  upper = x.size();
  while (lower + 1 != upper) {
    mid = (upper + lower) / 2;
    partition(x, lower, mid, upper); // O(upper - lower) time
    sumb = 0;
    maxb = 0; // assuming non-negative to avoid use of flags
    for (i = lower; i < mid; i++) {
      sumb += x[i];
      maxb = max(maxb, x[i]);
    }
    if (sumBelow + sumb + maxb * (x.size() - mid) <= s) {
      lower = mid;
      sumBelow += sumb;
    } else {
      upper = mid;
    }
  }
  K = (s - sumBelow) / (x.size() - lower);
  if (K > maxElement(x)) return error();
  else return K;
}