algorithm - 統計モードの計算

Question

現在、長さ N のソートされていない配列 A と整数 k を指定して、n/k 回以上発生する要素が存在するかどうかを検証しようとしています。

この問題に対する私の考えは、モードを計算し、これを n/k と比較することでした。ただし、このモードをすばやく計算する方法がわかりません。私の最終結果は n log(k) である必要がありますが、これを行う方法が本当にわかりません。私が見つけることができた最も速いのはn kでした...

Answer 1

m = n/k を切り上げます。クイックソートを実行しますが、長さが m 未満のサブリストは破棄します。

クイックソートと同様に、不運に見舞われて、端に近いピボットを繰り返し選択する可能性があります。ただし、ピボットをランダムに選択した場合、これが発生する可能性はわずかです。

再帰には O(log(k)) レベルがあり、各レベルには O(n) 時間がかかります。

Answer 2

シングルモードのデータセット（整数）のF＃.netでの統計モードの計算

let foundX (num: int, dList) = List.filter (fun x -> x = num) dList
let groupNum dList =
    dList
    |> (List.map (fun x -> foundX (x, dList)))
    |> (List.maxBy (fun x -> x.Length))

let Mode (dList: int List) = 
    let x = groupNum dList
    x.Head

//using Mode
let data = [1;1;1;1;1;1;1;1;2;2;3;3;3;1;4;4;4;4;4]
Mode data;;`

Answer 3

擬似コード:

 found = false
 value = null
 B = new hashtable
 for (i =0, j = A[i]; i < |A| and !found; ++i, j=A[i])
    if B contains key j
       B[j] = B[j] + 1
       if B[j] > |A|/k
          found = true
          value = j
       endif
    else 
       B[j] = 1
    endif
 end for

ハッシュテーブルの実装に O(1) 挿入/ルックアップがあると仮定すると、これは O(n) になるはずです