実数の配列の各要素の頻度を見つける最速のアルゴリズム？

Question

問題は、実数の配列の各要素の頻度を見つけることです。

まず解はO（n^2）：

for (int i = 0; i < a.length; i++) { 
    if (freq[i] != -1) { 
    for (int j = i + 1; j < a.length; j++) { 
     if (a[i] == a[j]) { 
     freq[i]++; 
     freq[j] = -1; 
     } 
    } 
    } 
} 

第二の溶液のO（nlogn）：私は2つの解決策が出ている

double[] a = new double[n] 
int[] freq = new int[n] 

quickSort(a, 0, a.length - 1); 

freq[j] = 1; 
for (int i = 0; i < a.length - 1; i++) { 
    if (a[i] == a[i + 1]) { 
    freq[j]++; 
    } 
    else { 
    j = i + 1; 
    freq[j] = 1; 
    } 
} 

されていますこの問題のためのより高速なアルゴリズムがあります（O（n）かもしれません）？ お手数ですがお寄せいただきありがとうございます。

Answer 1

心配することは誤り、あなたが

Map<Double, Long> freqCount = DoubleStream.of(reals).boxed() 
     .collect(Collectors.groupingBy(d -> d, Collectors.counting())); 

のようなハッシュマップを使用することができますこれは、メモリのかなりを使用していますが、O（n）があります。

代替は、これはまったく同じであるすべての値をカウントします

NavigableMap<Double, Long> freqCount = DoubleStream.of(reals).boxed() 
     .collect(Collectors.groupingBy(d -> d, TreeMap::new, Collectors.counting())); 

最初のパスとして、以下を使用することで、あなたはほぼ同じで、二重の値を結合するためにグループ化戦略を使用することができますあなたの目的のために等しいと考えられるべきです。これはO（N log N）

Answer 2

まず、doubleの身元を確認することは良い方法ではないと言うことから始めましょう。詳細はWhat every programmer should know about floating pointsを参照してください。
より堅牢なdoubleの比較を使用する必要があります。

今、私たちはこれで終わりました。あなたの問題に直面しましょう。
Element Distinctness Problemのバリエーションを浮動小数点数で扱っています。

一般に、代数木計算モデルの下では、Omega(nlogn)（このスレッド内の参照：https://stackoverflow.com/a/7055544/572670）よりもうまくいくわけではありません。 histogramベース

あなたは（しないでください）doubleの身元確認に固執しようとしている場合は、あなたがO(n)ソリューションを実現する強力なモデルや、ハッシュテーブルを使用することができ、ハッシュ・テーブルを維持することによっては、（として実装しますHashMap<Double,Integer>）を入力し、完了したらヒストグラムをスキャンして最も高い値のキーを返します。
（それをしないでください）

---

浮動小数点を扱う場合でも、ハッシュに基づいてO(n)時間を達成行うには、複雑な方法があります。これは、要素をハッシュテーブルの複数のエントリに追加し、ハッシュ関数が同じ範囲の要素[x-delta/2,x+delta/2)を同じハッシュ値（つまり、チャンクでハッシュしているため[x1,x2)->h1, [x2,x3)->h2, [x3,x4)->h3, ....）にすると仮定します。次に、要素xが3つの値にハッシュされるハッシュテーブルを作成できます。x-3/4delta, x, x + 3/4delta。
これは、後で等しい値をチェックするときに、要素を置く場所の少なくとも1つに一致することを保証します。

これは実装するのがはるかに複雑ですが、機能するはずです。これの変形は、cracking the code interviewで数学、質問6.（ちょうどあなたが版5を見て確認して、版4で答えが間違っているとは新版で修正された）別の側面として

---

を見つけることができます独自のソートを実装する必要はありません。 Arrays.sort()

Answer 3

挿入が非常に速くなる（または実数のオーダーと同じくらい速くなる）ため、Trieを使うと線形時間がかなり短縮されます。

周波数が必要なだけであれば、並べ替えとカウントが非常に遅くなります。あなたの友人はトライです：https://en.wikipedia.org/wiki/Trie

Trieを使用していた場合は、各整数をString（Javaで十分簡単）に変換します。 Trieへの挿入の複雑さは、実装に応じてわずかに異なりますが、一般的にはStringの長さに比例します。

あなたがトライの実装が必要な場合は、私はここに彼のアルゴリズムのコースのロバート・セジウィックの実装を検討してお勧め：あなたのダブルスはすでに適切に四捨五入されている、あなたはそこではありません確信している

http://algs4.cs.princeton.edu/52trie/TrieST.java.html