2

達成したいことが 2 つあります。1) ロトの結果からペア番号を見つけて、ハッシュ テーブルに格納します。2) 効率的な方法で宝くじの結果をループし、頻度を数え、頻度の結果をペア番号ハッシュ テーブルに追加します。

ペア数の頻度を教えてくれるプログラムを作りたいです。

For a list / array of number , example :
    4, 12, 20 , 32, 48, 50
    2, 22, 20 , 32, 38, 40
    4, 12, 20 , 25, 33, 44
    1, 11, 20 , 31, 48, 50
    1, 12, 20 , 36, 47, 51

私が望む結果：

    Pair Number     |      Repeat Times
    4, 12                          2
    4, 20                          2
    12, 20                         3
      .                            .
      .                            .

可能なすべてのペア番号のリストを自動化
リスト/配列に不要なデータ。簡単にグループ化できるようにデータを保存するための別の推奨事項はありますか? マップ？

ループ以外の繰り返し数をグループ化してカウントする効率的な方法はありますか?

提案やアドバイスに感謝します。

4

1 に答える 1

0

わかりやすくするために、要素 (またはこの場合は数値) でn構成されるセットから始めるとしましょう。c問題は、すべてのセットのサイズ 2 のすべての一意のサブセットの集計頻度 (つまり、すべてのセットにまたがる) を見つけることです。

これを行うには、各セットをループして、そのセット内の要素のすべてのペアを考慮し、その頻度をハッシュ テーブルに維持します。ペアを検討するとき、ハッシュ テーブルに既に存在する場合は、その値に 1 を追加します。それ以外の場合は、値 1 でハッシュ テーブルに追加します。コードは、以下の疑似コードに漠然と似たものになります。

hashtable h
for s in sets:
   for i in s.size():
       for j > i in s.size():
            pair p = (s[i],s[j])
            if h.exists(p):
                h[p]++
            else:
                h.put(p,1)

nこのアプローチには、c、およびの制限を持つ 3 重にネストされたループがあるためc、このアルゴリズムはO(nc^2)時間内に実行されます。

サイズ 2 のすべての可能なサブセットが一意であるという極端なケースを考えてみましょう。このような場合、頻度のテーブルはn × c choose 2要素で構成されます。big-O 表記では、この値は に減少しO(nc^2)ます。したがって、最良の解は、O(nc^2)正確に上記のアルゴリズムの速度である よりも優れているわけではありません。

于 2012-06-30T07:37:25.557 に答える