arrays - 在未排序的数组中找到一个元素“k”，使得有“k”个大于该元素的元素

Question

Accolite采访：

输入：整数数组（未给出范围），未排序，大小 n

输出：在数组中找到一个元素“k”，使得数组中正好有“k”个元素大于这个元素。

例如，如果数组是：

1. [4,3,6,9,10,22] 这里的输出是4

2. [4,3,6,9,10] 输出：没有找到这样的数字

这个问题可以很容易地通过在 O(n log n) Time 中排序来完成，但我被要求在 O(n) 时间内完成（如果 O(logn) 可能的话）。

Answer 1

有人帮忙，这是解决方案

注意点：“K”不能大于数组的大小。 我们将有一个大小等于给定数组的计数数组。

assuming indexes start from 1 
for(i=1;i<=n;i++)
{
  if(a[i]<=n)
    count[a[i]-1]++;
  else
    count[n]++;
}



boolean flag=false;
 for(i=n-1;i>=1;i--)
 {
    if(count[i]==i)
    {
      flag=true;
      System.out.println("k: "+i);

    }
 }

 if(flag==false)
      System.out.println("No such number found);

}

Answer 2

int[] count = new int[ n + 2 ];
for ( int k = 0; k < n; ++k )
    ++count[ Math.min( n + 1, Math.max( 0, a[ k ] + 1 ) ) ];
int k = n, c = count[ n + 1 ];
for ( ; k > 0 && ( 0 == count[ k ] || k != c ); c += count[ k-- ] );
System.out.println( 0 == k ? "not found" : "found: " + k );