5

最近どこかで出会ったこの本当に良いインタビューの質問があり、これに対する最も最適化された解決策は何かをすべての天才に尋ねたかった. したがって、問題は次のとおりです。整数の配列が与えられた場合、n より大きい配列要素が少なくとも n 個存在するような最大数 n を見つけます。入力配列はソートされていません。

例:

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

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

私が考えることができる1つの解決策（配列がソートされている場合）は、配列内のすべての要素を順次スキャンして、min：nとmax：nを見つけることです。次に、min:n から max:n までの整数をインクリメントし、1 つずつチェックアウトします。しかし、これは 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 の検索とも呼ばれます

4

6 に答える 6

9

編集：O(n)ソートされていないケースの解決策を見つけました:)以下を参照してください！

並べ替え:

O(log Nこれは、 の二分探索によって、ソートされた配列について ) で解決できますn。ここでは OP の表記法を使用しますN = # of elements。 とnは探している答えです。

配列がソートされている場合、それは基本的[N - n]に、配列内のそのような位置により大きい値が含まれるように位置を見つける必要があることを意味しますn-もしそうであれば、繰り返される値に関係なく、少なくともnそれより大きい値があります。

最悪の場合の答えは であり、それよりも大きい要素0は常に少なくとも0 個あるため、答えは常に可能であることに注意してください。明らかに、10 より大きい 10 個の要素よりも 1 より大きい 1 個の要素を見つける方が簡単であるため、値が小さいほど答えは常に「より簡単」になります。それにバイナリ検索を使用します。

考え方は次のとおりです。

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です。二分探索が valuen = 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

ここで、その値が(この場合は )よりも大きい場合、上で示したように、少なくともよりも大きい要素があるため、配列の下半分をさらに検索するだけで済みます。(中央値が より小さい場合、代わりに配列の大半分のみを考慮します)nN/2nnn

ここで、インデックスからmedian >= N/2まで同じプロセスを繰り返し、で「並べ替え」を選択するなどして、毎回検索空間を 2 で割ると仮定します。[0][N/2]O(N/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)

于 2013-07-02T04:45:05.890 に答える
4

魔法は関係ありません

上記を読んで、「インタビューでどうやってそれを思いつくのか」または「このコードにバグがないことを本当に信頼できるか」と思った場合は、もう探す必要はありません! 「フォーマルプログラムデザイン」の楽しい世界をご紹介します！

この回答では、問題ステートメントを不等式のペアに変換する方法を説明します。これにより、二分探索が強制されるため、それを記述する方法は 1 つだけです。また、以前の回答で除外されたいくつかのバグと特殊なケースもキャッチします。

すべての設定

size のソートされた空でない配列があると仮定しましょうN=7。

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

私たちが本当に欲しいのはistです

ar[i] <= N-i-1

ただし、最大のもの、つまり最も右にあるものが必要なので、次のようにする必要があります。

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

フォーマルになる

これから行うことは、2 つの変数loとhist を保持することです。私たちはいつも持っています

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

i+1(2 番目の式のforの置換に注意してくださいhi)。

次に、最初に求めlo+1 = hiていた が見つかった時点で、変数を互いに向かって慎重に移動させます。i

ここで、いくつかの開始値が必要です。

  • の選択肢hiはN. これは配列の範囲外ですが、読み取ることはないので、式 (2) を満たす巨大な値であると仮定します。

  • そのloような値が存在することさえ確認できるのでしょうか? いいえ！配列[7,8,9]には、必要なプロパティを満たすインデックスがないため、最初のコーナー ケースが見つかりました。いずれかのインデックスが (1) を満たす場合、それは である必要があると想定できますが0、続行しても実際に問題がないかどうかを確認するテストを導入する必要があります。

甘い！厄介なバグを回避しました。

コードにプラグインする

わかりました。この時点で、二分探索を呼び出します。実際、作業はすでに完了しており、単純に次のように記述します。

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

楽しみのために、同じ配列で「i Code 4 Food」のコードも実行してみました。彼は戻ってきたので、値が一意であると想定していると思います

lo = 4

ar[4] = 6であり、その後に値が 2 つしかないため、これは明らかに機能しません。

于 2013-09-19T11:05:21.590 に答える
0

「i Code 4 Food」の回答は実に素晴らしいものです。

しかし、別の方法で開始点を決定できると思います (これがより良いかどうかはわかりません)。

与えられた条件を満たす要素をnとします。ここで、ソートされた配列から要素をランダムに選択したいとします (整数の確率変数をXとします)、次にP( X > n) >= n/N (N は配列内の要素の総数)。

しかし、マルコフの不等式から、P( X > n) <= E[X]/nが得られます。ここで E[X] は期待値、つまりこの場合の平均です。

上記の 2 つの不等式を考慮すると、n/N <= E[X]/n、つまりn^2 <= Sumとなります。

たとえば、 Input : 1,2,5,7,8,10 を考えてみましょう。不等式n^2 <= 33からn < 6になります。したがって、ここに出発点を設定することもできました。

于 2013-07-02T06:34:27.390 に答える
-1

ウィリアム・ゲイツの回答に対する私の編集が「製品またはサービスの宣伝」のために拒否されたので(何?)、彼のソリューションを実装するコードをここにコピーしました。C++ では、これは次のように保証された線形時間で任意のデータ セットに対して実装できます。

#include <algorithm>
#include <vector>

size_t solve(std::vector<int> const &input) {
    std::vector<size_t> counts(input.size() + 1, 0);
    for (auto val : input) {
        if (0 <= val)
            ++counts[std::min(static_cast<size_t>(val), input.size())];
    }
    size_t n{ input.size() };
    for (size_t numGreater{ counts[n] }; 0 < n
         && numGreater < n; numGreater += counts[--n]);
    return n;
}

これには、O(N) の追加メモリと O(N) の時間が必要であることに注意してください。

于 2019-03-01T01:34:23.603 に答える