arrays - 数据结构面试: find max number in array

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 min: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)未分类案例的解决方案 :) 见下文!

已排序:

这可以在 O(log N 中解决) 对于排序数组，通过对 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 个元素是否大于 5。在这种情况下，8 > 5所以我们可以尝试更好的答案。然后搜索将尝试 7 , 但位置为 [N-7] 的元素是5 ，低于 7，不满足我们的约束条件。因此搜索的最后一次尝试是值 6 ，返回 true 作为 7 > 6 .

未排序:

对于未排序的情况，这个想法非常相似!我们可以在O(n)解决通过使用 Selection Algorithm识别第[N-n]个元素，并在每一步以与二进制搜索相同的方式划分搜索空间。

我们从 [0] 开始搜索至 [N-1]找到中位数 (N/2 th) 元素，我们可以在另一个 O(N) 中重新排列数组步骤使得中间元素被放置在正确的位置，并且它之前的每个元素都具有值 <= median ，而它后面的每个元素都有一个值 >=median .

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

现在，假设 median >= N/2我们将从索引 [0] 重复相同的过程至 [N/2] , 在 O(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) 的复杂度