数据结构面试:在数组中查找最大数

Question

最近我在某个地方遇到了一个非常好的面试问题，我想问你们所有的天才，什么是最优化的解决方案。所以问题如下:给定一个整数数组，找到一个最大数n，使得至少有n个数组元素大于n。输入的数组是未排序的。

例如：

输入: 1,2,5,7,8,10输出:n=4

输入: 0,2,7,8,19,5,45,9,23输出:n=6

我能想到的一个解决方案(如果数组是排序的)是对数组中的所有元素进行顺序扫描，找出min:n和max:n，然后在min:n到max:n之间递增整数，并逐个检查。但这是O(N)解。有没有人能推荐一个更好的？

例如:对于输入1分钟:n=2和max:n =5

然后，您将检查数字2、3和4作为答案。

根据答案，如果数组未排序，则没有比O(N)更好的解决方案。但是下一个问题是，如果给定的数组是排序的，该怎么办？

pseudocode :
// this assumes sorted input.
pubic int findhighestIndex(List<Integer> input){
it min=0,max=0,n=0,maxIndex=0;
for(int i=0;i<input.size();i++){
    if( input.get(i)>(input.size()-i) ){
        max=input.get(i);
        maxIndex=i;
        min=input.get(i-1);
        break;
    }
    else if(input.get(i)<(input.size()-i)){
        max=min=input.get(i);
    }
}
int i=max;
while( i>=min && (input.size()-maxIndex)<i ){
i--;
}
System.out.println(i);
}

更新:这个问题也被称为查找h-index

Answer 1

编辑：刚刚想出了针对未排序情况的O(n)解决方案:)如下所示！

排序：

这可以通过n上的二进制搜索在排序数组的O(log N中得到解决。我将在这里使用OP的表示法，其中N = # of elements和n是我们要寻找的答案。

如果数组被排序，这基本上意味着我们需要找到一个位置[N - n]，以便数组中的这个位置包含一个大于n的值-如果是这样，那么至少有n值大于它，而不管重复的值。

注答案总是可能的，因为在最坏的情况下，答案将是0，并且总是至少有0个元素大于它。显然，对于较低的值，答案总是变得“更容易”，因为找到1个大于1的元素比找到10个大于10的元素更容易。但更重要的是，该函数遵循单调(非递减)行为，允许我们对其使用二进制搜索。

其思路如下：

int N = 9;
int arr[10] = {0,2,5,7,8,9,19,23,45};

int lo = 0, hi = N+1, mid;
while(hi-lo > 1){
    mid = (hi+lo)/2;
    if(arr[N-mid] > mid) lo = mid;
    else hi = mid;
}
n = lo; //highest value that worked

细目:数组的大小为9。二进制搜索可能会开始尝试取值n = 5，因此我们只检查数组末尾的第五个元素是否大于5。在这种情况下，取值为8 > 5，这样我们就可以尝试更好的答案。然后搜索将尝试7，但是位置[N-7]处的元素是5，它小于7并且不满足我们的约束。因此，搜索的最后一次尝试是作为7 > 6返回true的值6。

未排序：

对于未排序的情况，想法非常相似！我们可以通过使用Selection Algorithm来识别第N个元素，并在每个步骤中以与二进制搜索相同的方式划分搜索空间，从而在O(n)中解决此问题。

我们首先从[0]搜索到[N-1]，以找到中值(N/2 th)元素，然后我们可以在另一个O(N)步骤中重新排列数组，以便将中值元素放置在其正确的位置，并且它之前的每个元素都具有值<= median，而它之后的每个元素都具有值>=median。

现在，如果该值大于n (在本例中为N/2)，我们在上面显示了至少有n元素大于n和，因此我们只需要在数组的下半部分中进一步搜索。(如果中值低于n，我们只考虑数组的大半部分)

现在，假设排序，我们将重复从索引[0]到[N/2]的相同过程，在O(N/2)中使用选择“median >= N/2”，依此类推，每次将搜索空间除以2。

C++代码如下：

int N = 9;
int arr[9] = {0,2,7,8,19,5,45,9,23};

int lo = 0, hi = N, mid;
while(hi-lo > 1){
  mid = (hi+lo)/2;
  std::nth_element(arr+lo, arr+mid, arr+hi);
  if(arr[mid] > N-mid) hi = mid;
  else lo = mid;
}
n = N-hi;

最后，我们实现了O(N) + O(N/2) + O(N/4) + ... = O(2*N) = O(N)的复杂度

Answer 2

不涉及魔法

如果你一直在读上面的文章，并且在想“我怎么才能在面试中想到这一点”，或者“我真的可以相信这段代码没有bug”，那么就别再看了！让我向你介绍“形式化程序设计”的快乐世界！

在这个答案中，我将解释如何将问题陈述转化为一对不等式，这反过来将迫使我们进行二进制搜索，所以只有一种方法来编写它。我还将捕获一些在前面的答案中遗漏的bug和角落案例。

设置好一切

让我们假设我们有一个大小为N=7的排序的非空数组。

N: 7
    i: 0 1 2 3 4 5 6
ar[i]: 3 3 4 5 6 6 7

我们真正想要的是一个i s.t.

ar[i] <= N-i-1

但是，我们想要最大的那个，也就是最右边的那个，所以它必须是

ar[i+1] > N-i-1

变得正式

我们要做的是保留两个变量lo和hi st。我们一直都有

ar[lo] <= N-lo-1   (1)
ar[hi] > N-hi-1    (2)

(请注意，在第二个等式中用i+1替换hi )。

然后，我们将小心地将变量相互移动，直到lo+1 = hi，在这一点上，我们找到了我们最初寻找的i。

现在我们需要一些起始值。

• hi的一个选择可能是N。这超出了数组的范围，但我们永远不会读取它，所以我们假设它是一个满足等式(2)的巨大值，

，

• ，lo更难，因为我们能确定这样的值是否存在吗？不是的！数组[7,8,9]没有满足所需属性的索引，因此我们找到了第一个角例。我们可以假设，如果任何索引满足(1)，则它一定是0，但我们必须引入一个测试，以查看是否确实可以继续。

甜!我们避免了一个讨厌的bug。

将其插入到代码中

好了，现在是调用二进制搜索的时候了。实际上，这项工作已经完成了，我们只需编写：

if ar[0] > N-0-1:
    panic("No solutions found!")

lo, hi = 0, N
while lo+1 != hi:
    mid = (lo + hi)/2
    if ar[mid] <= N-mid-1:
        lo = mid
    if ar[mid] > N-mid-1:
        hi = mid

print "The solution is ar[%d] = %d" % (lo, ar[lo])

(请注意，我们可以将第二个if更改为else，因为条件是彼此的倒数)

结果

在原始示例上运行它会给出以下结果：

The solution is ar[2] = 4

为了好玩，我还试着用相同的数组运行“ICode4Foot”的代码。

lo = 4

这显然是行不通的，因为ar[4] = 6，在那之后只有两个值。

Answer 3

不需要排序。

如果a1...N是输入数组，那么请注意您正在寻找的答案是<= N。

所以对于0，<=，i，<=，N中的每个数字i，我们尝试跟踪>i的元素数量。

为了在O(N)时间内计算它，我们分配一个大小为N+1的数组S，初始化为零。

当您遇到元素a (= aj)时，如果a> N，则递增SN+1，否则递增Sa。

元素的数量>i将由Si+1 + Si+2 + ... + SN+1给出。

我们可以通过从N+1到1遍历S来计算每个i的总和，并保持累积和。