arrays - N 個の要素を持つ整数配列で、最小の k 個の要素を見つけますか?

Question

重複の可能性:
k 選択を行うための最悪の O(n) アルゴリズム

次の質問があるとします。

In an integer array with N elements , find the minimum k elements (k << N)

Nかなりの数であると推測できます。

私は最小のヒープについて考えていますが、誰かがより良い解決策を持っていますか?

よろしく

Answer 1

K << N の場合、ヒープの作成は O(n) であるため、最小ヒープで十分です。また、K << N の場合、最初の K 個のアイテムを選択するのは最大で O(N) です。それ以外の場合は、選択アルゴリズムを使用して K 番目に小さい要素を見つけることができます。O(n)次に、見つかったアイテムよりも小さい数字を選択します。(一部の数値が K 番目の要素と等しい場合は、K項目を埋めるまで選択してください)。

Answer 2

これはどうですか：

配列をソートし (クイックソートまたはヒープソートは整数配列に最適です)、k まで繰り返します。

Answer 3

これは O(N*log(K)) でできると思います。擬似コード:

haz array[N]
haz output[k] (itz a list)

i iteratez on array with array[N] az element:
    i insertz element into output (i maintainz strict ordering)
    i removez largest element of output when output size iz bigger than k

必要：

• 末尾から N 個のリストを削除 (N * O(1))
• 最大 N 回のソート維持リスト挿入 (N * O(log(listsize)))

リストのサイズは K によって制限されます

したがって、O(N * log(K)) 時間です。