java - 多数の整数の中央値を見つける方法 (メモリに収まらない)

Question

答えは中央値の中央値を使用していることは知っていますが、誰かがその方法を説明できますか?

Answer 1

これを行うための線形時間アルゴリズムがあります。このページが役立つかもしれません。

基本的に、選択アルゴリズムの動作はクイックソートに似ていますが、毎回ピボットの側でのみソートされます。目標は、見つけようとしていた要素のインデックスに等しいピボットを選択するまで、分割を続けることです。これは、quickselect 用に見つけた Java コードです。

public static int selectKth(int[] arr, int k) {
 if (arr == null || arr.length <= k)
  throw new Error();

 int from = 0, to = arr.length - 1;

 // if from == to we reached the kth element
 while (from < to) {
  int r = from, w = to;
  int mid = arr[(r + w) / 2];

  // stop if the reader and writer meets
  while (r < w) {

   if (arr[r] >= mid) { // put the large values at the end
    int tmp = arr[w];
    arr[w] = arr[r];
    arr[r] = tmp;
    w--;
   } else { // the value is smaller than the pivot, skip
    r++;
   }
  }

  // if we stepped up (r++) we need to step one down
  if (arr[r] > mid)
   r--;

  // the r pointer is on the end of the first k elements
  if (k <= r) {
   to = r;
  } else {
   from = r + 1;
  }
 }

 return arr[k];
}

Answer 2

この質問に対する最初の 2 つの回答を参照してください。最初のもの（頻度カウント）がデータ/利用可能なストレージで機能する場合、その方法で正確な答えを得ることができます. 2 つ目 (修復) は、堅牢で一般的な方法です。