9

これはおそらくマイクロソフトのインタビューの質問です。

ソートされた配列から k 番目に小さい要素 (重複を無視) を見つけます。
[編集] : 配列には重複が含まれる場合があります (指定されていません)。

何度も考えましたが、まだ自問自答しています:もっと良い解決策がまだありますか?

アプローチ 1:

最大ヒープを取得し、最初の k 個の一意の要素を挿入します [簡単に確認できます]。ヒープをヒープ化します。
ここで、新しい要素がヒープのヘッドよりも小さい場合、ヘッドをこの新しい要素に置き換えてヒープ化します。最後に、ヒープのサイズが k の場合、ヒープの先頭は k 番目に小さい要素を示します。そうでない場合、k 番目に小さい要素は存在しません。

時間計算量: O(NlogK)
空間計算量: O(K)

アプローチ 2[より良いアプローチ]:

要素は正しく複製できます。そのため、前の要素と比較して一意の要素を確認し、これまでに見つかった一意の変数が k までカウントされたら停止します。
時間の複雑さ: O(N)
空間の複雑さ: O(1)

アプローチ3[より良いアプローチ（かもしれません）]：

クイック ソート パーティション アルゴリズムの修正版も使用できます。しかし、配列がすでにソートされているため、最悪のケースにつながる可能性があります。
ここで 2 つの疑問が生じます:
1.配列に重複が含まれていても機能しますか?
2. 2 番目のアプローチよりも優れていますか?

O（logn）ソリューションが存在するのではないかと思っていましたか？

4

2 に答える 2

8

O(kLogN) ソリューションは次のとおりです。

バイナリ検索のバリエーションを使用して、特定の値の最後の出現を見つけます。

  1. 最初の値 - O(1) を取得します。
  2. この値 O(logN) の最後の出現を検索し、次の要素を調べて 2 番目の値 - O(1) を取得します。
  3. k 番目の値が見つかるまで繰り返します。
于 2012-06-21T17:46:37.070 に答える
5

k番目に小さい要素には 2 つの異なる解釈があるようです。私はそれが「重複を無視してk番目に小さい要素」を意味すると仮定しています。

最善の解決策は、アプローチ 2 で説明したように、O(n) 時間と O(1) 空間です。これを証明できます。

  • O(1) 空間を改善することはできません (少なくとも O 表記では)。
  • O(n) 未満で実行されるアプローチを検討してください。このようなアプローチでは、配列内の各要素を考慮してはなりません。そのような見逃された要素の 1 つを考えてみましょう。この要素がその前または後の値の複製であるかどうかはわかりません¹。この情報は、配列内のどの値がk番目に小さい値に対応するかをアサートするために必要です。

¹ 隣接していない 2 つの配列要素が同じ値を持つ特殊なケースでは、並べ替えられた配列の任意の長さのサブシーケンスの値を推測することができます。すべての中間要素がその値を共有する必要があります。しかし、これは典型的なケースではないので、無視しています。

于 2012-06-21T17:41:17.430 に答える