-2

アコライト インタビュー:

入力: 整数の配列 (範囲指定なし)、ソートなし、サイズ n

出力: 配列内の要素 "k" を見つけて、この要素よりも大きい "k" 要素が配列内に存在するようにします。

たとえば、配列が次の場合:

1. [4,3,6,9,10,22] ここでの出力は 4

2. [4,3,6,9,10] 出力: No such number found

この質問は、 O(n log n) Time でソートすることで非常に簡単に実行できますが、O(n) 時間 (および O(logn) が可能な場合) で実行するように求められました。

4

2 に答える 2

0

誰かが助けてくれました、ここに解決策があります

注意点：「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);

}
于 2013-09-08T08:31:26.920 に答える
0 
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 );
于 2013-09-21T09:03:17.833 に答える