0

したがって、一連の数字を持つ n 個のグループが与えられた場合 (特定のグループで数字が繰り返されることはありません。2 つ以上のグループで alteast に 2 回現れる数字を検索するにはどうすればよいですか?

例えば：

A: 1,2,3,4,5

B: 1,6,7,8,9

C:3.10,11,12

答えは : 3 つのグループで少なくとも 2 回出現するため、1 と 3 です。

グループ x の各要素をグループ Y の別の要素などと比較してみましたが、これは効率的ではなく、より大きなデータの計算には長い時間がかかります。

4

5 に答える 5

5

アイテムのセットに重複する要素が含まれているかどうかを判断するより効率的な方法の 1 つは、HashSet を使用することです。すべての要素を調べて HashSet に追加しますが、要素を追加する直前に、HashSet にその項目が既に含まれているかどうかを確認します。アイテムが HashSet に既に存在する場合、そのアイテムは既に別の場所に存在し、重複しています。

このアプローチでは、データがソートされていることを確認する必要はありません。データの並べ替えはせいぜい O(n lg n) です。HashSet アプローチは単なる O(n) です。

コメントの混乱を明確にするために、アルゴリズムの疑似コード バージョンを次に示します。

for Integer e in allLists {
    if (hashSet.contains(e)) {
        //e was added in a previous iteration of the loop and thus e is a duplicate
        results.add(e);
    } else {
        hashSet.add(e); 
    }
}
于 2013-08-12T15:37:23.573 に答える
2

グローバルHashMap<Integer, Integer>を使用して、配列に表示された各数値のカウントを保持します。

として宣言されているため、リストに重複する要素が含まれることはありません。2 つ以上のリストにある数値を見つけるには、マップのキーセットを反復処理し、対応するcounter.

複雑さ:O(N)はNリスト配列内の整数の総数です。

于 2013-08-12T15:41:34.383 に答える