16

中央値選択アルゴリズムの中央値を使用して、O(n) の中央値を見つけることができます。また、アルゴリズムが完了した後、中央値の左側にあるすべての要素は中央値よりも小さく、右側にあるすべての要素は中央値よりも大きいことがわかっています。しかし、O(n) 時間で中央値に最も近い k 個を見つけるにはどうすればよいでしょうか?

中央値が n の場合、左側の数値は n 未満であり、右側の数値は n より大きいです。ただし、配列は左側または右側でソートされません。数値は、ユーザーが指定した個別の数値の任意のセットです。

問題は、Cormen によるアルゴリズムの紹介、問題 9.3-7 からのものです。

4

13 に答える 13

20

誰もこれを完全に持っているようには見えません。方法は次のとおりです。まず、上記のように中央値を見つけます。これは O(n) です。ここで、中央値を配列の最後に置き、他のすべての要素から中央値を減算します。ここで、再度クイック選択アルゴリズムを使用して、配列の要素 k (最後の要素を含まない) を見つけます。これは、要素 k を (順番に) 見つけるだけでなく、最小の k 個の数値が配列の先頭になるように配列を残します。中央値を追加すると、これらは中央値に最も近い k になります。

于 2012-05-09T06:08:59.913 に答える
10

中央値の中央値は、少なくとも n が大きい場合、最近傍を見つけるのにおそらくあまり役​​に立ちません。確かに、5 つの各列が中央値で分割されていますが、これは問題を解決するのに十分な順序情報ではありません。

中央値を中間結果として扱い、最も近い隣人を優先キューの問題として扱います...

中央値の中央値から中央値を取得したら、その値を書き留めます。

すべてのデータに対して heapify アルゴリズムを実行します - Wikipedia - Binary Heapを参照してください。比較では、その保存された中央値との相対的な差に基づいて結果を出します。最も優先度の高い項目は、ABS(値 - 中央値) が最も低い項目です。これには O(n) かかります。

配列の最初の項目は中央値 (またはその複製) になり、配列はヒープ構造を持ちます。ヒープ抽出アルゴリズムを使用して、必要な数の最近傍を引き出します。これは、k 個の最近傍の O(k log n) です。

k が定数である限り、中央値の O(n) 中央値、O(n) ヒープ化、および O(log n) 抽出が得られ、全体として O(n) が得られます。

于 2009-10-13T01:18:58.647 に答える
4 
med=Select(A,1,n,n/2)   //finds the median

for i=1 to n
   B[i]=mod(A[i]-med)

q=Select(B,1,n,k) //get the kth smallest difference

j=0
for i=1 to n
   if B[i]<=q 
     C[j]=A[i] //A[i], the real value should be assigned instead of B[i] which is only the difference between A[i] and median.
       j++
return C
于 2010-09-08T13:59:30.807 に答える
3

次のように問題を解決できます。

O(n) nth_element アルゴリズムを使用して、O(n), wg の中央値を見つけることができます。

それぞれをペアに置き換えて、すべての要素をループします。

the absolute difference to the median, element's value.

もう一度、n = k で nth_element を実行します。このアルゴリズムを適用すると、新しい配列の最初に絶対差の k 個の最小要素を持つことが保証されます。あなたは彼らのインデックスを取り、DONE！

于 2013-07-03T15:15:14.027 に答える
2

4 つのステップ:

  1. 中央値の中央値を使用して、配列の中央値を特定します - O(n)
  2. 中央値と配列内の各要素との絶対差を決定し、それらを新しい配列 O(n) に格納します
  3. QuickselectまたはIntroselectを使用して、新しい配列から k 個の最小要素を選択します - O(k*n)
  4. 元の配列にインデックスを付けて k 最近傍を取得 - O(k)

k が十分に小さい場合、全体の時間計算量は O(n) になります。

于 2018-08-13T07:36:53.420 に答える
0

O(n) で中央値を見つける方法は既に知っています

順序が重要でない場合、最小の k の選択は O(n) で行うことができます。最小の k は中央値の右辺に、最大の k は中央値の左辺に適用されます。

ウィキペディアから

 function findFirstK(list, left, right, k)
 if right > left
     select pivotIndex between left and right
     pivotNewIndex := partition(list, left, right, pivotIndex)
     if pivotNewIndex > k  // new condition
         findFirstK(list, left, pivotNewIndex-1, k)
     if pivotNewIndex < k
         findFirstK(list, pivotNewIndex+1, right, k)

k==n が元のリストを返す特殊なケースを忘れないでください

于 2009-10-13T01:35:57.690 に答える
0

number のリストで基数ソートなどの非比較ソートを使用し、Lk 個の要素のウィンドウを考慮してウィンドウの端点を調べることで、k 個の最近傍を見つけることができます。「ウィンドウを見つける」という別の言い方は、abs(L[(n-k)/2+i] - L[n/2]) + abs(L[(n+k)/2+i] - L[n/2])(k が奇数の場合) またはabs(L[(n-k)/2+i] - L[n/2]) + abs(L[(n+k)/2+i+1] - L[n/2])(k が偶数の場合) を最小化する find i です。ケースを組み合わせると、abs(L[(n-k)/2+i] - L[n/2]) + abs(L[(n+k)/2+i+!(k&1)] - L[n/2]). 最小値を見つける簡単な O(k) 方法は、i=0 から始めて、左または右にスライドすることですが、O(log(k)) で最小値を見つけることができるはずです。

最小化する式は、各要素の中央値からの差を取ることにより、L別のリスト に変換することから得られます。M

m=L[n/2]
M=abs(L-m)

iを最小化しM[n/2-k/2+i] + M[n/2+k/2+i]ます。

于 2009-10-13T01:40:49.007 に答える
0

実際、答えは非常に簡単です。必要なのは、中央値がインデックス m にあるときに、m-1 から 0 および m+1 から n-1 に移動する中央値からの絶対差が最小の k 要素を選択することだけです。2 つの並べ替えられた配列をマージする際に使用したのと同じアイデアを使用して、要素を選択します。

于 2009-10-14T03:51:22.493 に答える
-1

まず、その複雑さの標準アルゴリズムO(n)を使用して、時間の中央値を選択します。次に、中央値に最も近い要素を選択して、リストを再度実行します（最大の要素を検索するのと同じように、最もよく知られている候補を保存し、これらの候補と新しい値を比較します）。

この追加の実行の各ステップでは、O（k）ステップが必要であり、kは一定であるため、これはO（1）です。したがって、完全なアルゴリズムの合計実行時間と同様に、追加の実行に必要な時間の合計はO（n）です。

于 2009-10-13T00:52:20.017 に答える
-1

すべての要素が異なるため、平均値と同じ差を持つ要素は最大 2 つ存在する可能性があります。平均からの差の絶対値を表すインデックスである 2 つの配列 A[k] と B[k] を使用する方が簡単だと思います。ここでのタスクは、配列を埋めて、A[i+1] と B[i+1] の前に A[i] と B[i] を読み取る配列の最初の k 個の空でない値を読み取って、k 個の要素を選択することです。これは O(n) 時間で実行できます。

于 2009-10-13T02:43:58.117 に答える
-1

配列から中央値を減算することを提案するすべての回答は、誤った結果を生成します。このメソッドは、位置が最も近いのではなく、値が最も近い要素を見つけます。

たとえば、配列が1,2,3,4,5,10,20,30,40. k=2 の場合、返される値は (3,4) になります。これは正しくありません。最も近い隣人であるため、正しい出力は (4,10) になります。

結果を見つける正しい方法は、選択アルゴリズムを使用して上限要素と下限要素を見つけることです。次に、直接比較して、リストから残りの要素を見つけます。

于 2020-02-05T23:16:11.327 に答える
-1

中央値のインデックスがわかっている場合は、おそらく ceil(array.length/2) である必要があり、n(xk)、n(x-k+1)、...をリストするプロセスである必要があります。 、n(x)、n(x+1)、n(x+2)、... n(x+k) ここで、n は配列、x は中央値のインデックス、k は近傍の数です。あなたが必要です。

于 2009-10-13T00:44:50.917 に答える