7 
Find the nth most frequent number in array.
(There is no limit on the range of the numbers)

できると思います

（i）C++のマップを使用してすべての要素の出現を保存します

（ii）要素の出現（または頻度）の線形時間で最大ヒープを構築し、次にN番目の要素まで抽出します。各抽出はヒープ化するのにlog（n）時間を要します。

（iii）N番目に頻度の高い番号の頻度を取得します

（iv）次に、ハッシュを線形検索して、この頻度を持つ要素を見つけることができます。

時間-O（NlogN）スペース-O（N）

より良い方法はありますか？

4

4 に答える 4

8

それは線形時間と空間で行うことができます。Tを入力配列内の要素の総数とし、そこからN番目に頻度の高い数を見つける必要があります。

  1. マップ内のTのすべての数の頻度を数えて保存します。Mを配列内の個別の要素の総数とします。したがって、マップのサイズはMです。--O（T）
  2. 選択アルゴリズムを使用して、マップ内でN番目に大きい頻度を見つけます。--O（M）

合計時間=O（T）+ O（M）= O（T）

于 2012-08-01T13:15:37.163 に答える
3

あなたの方法は基本的に正しいです。構築されたヒープの各頂点にそれが表す番号をマークすると、最終的なハッシュ検索を回避できます。さらに、ヒープの5番目の要素を構築している間、常に監視し続けることができます。これは、ある時点で、結果が変更できなくなり、残りの計算がドロップされる可能性があるためです。しかし、これはおそらく一般的なケースではアルゴリズムを高速化せず、特別なケースでもそうではないかもしれません。だからあなたはあなた自身の質問に正しく答えました。

于 2012-06-10T02:37:55.677 に答える
1

それはあなたが最も効果的な方法を望むか、それとも最も書きやすい方法を望むかによって異なります。

1）すべての数値が0から1000になることがわかっている場合は、1000個のゼロ（オカレンス）の配列を作成し、配列をループして、正しいオカレンス位置をインクリメントします。次に、これらのオカレンスを並べ替えて、N番目の値を選択します。

2）ユニークなアイテムの「バッグ」があり、番号をループして、その番号がバッグに入っているかどうかを確認します。入っていない場合は追加し、ここにある場合は、発生数を増やすだけです。次に、そこからN番目に小さい数を選択します。

バッグは、線形配列、BST、または辞書（ハッシュテーブル）にすることができます。

質問は「N番目に多い」であるため、並べ替え（または巧妙なデータ構造）を避けることはできないと思います。したがって、最高の複雑さはO（n * log（n））よりも優れているわけではありません。

于 2012-06-10T02:32:30.437 に答える
1

Java8でメソッドを記述したばかりです。これは効率的なソリューションではありません。

  • 各要素の頻度マップを作成します
  • 値に基づいてマップコンテンツを逆の順序で並べ替えます。

  • （N-1）番目の要素をスキップして、最初の要素を見つけます

    private static Integer findMostNthFrequentElement(int[] inputs, int frequency) {
    return Arrays.stream(inputs).boxed()
        .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
        .entrySet().stream().sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
        .skip(frequency - 1).findFirst().get().getKey();
}
于 2018-12-15T19:24:02.913 に答える