数据结构访谈:在数组中查找最大数量

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和最大值: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)通过使用选择算法来识别[NN]个元素,并且在每个步骤作为二进制搜索划分搜索空间中相同的方式.

首先,我们从搜索[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)