8

double 配列で出現回数が最も多い要素を見つける必要があります。私はこのようにしました：

int max = 0;
for (int i = 0; i < array.length; i++) {
       int count = 0;
       for (int j = 0; j < array.length; j++) {
         if (array[i]==array[j])
             count++;
   }
  if (count >= max)
      max = count;
 }

プログラムは動作しますが、遅すぎます。より良い解決策を見つけなければならないのですが、誰か助けてくれますか?

4

12 に答える 12

13

アップデート：

HashMapを使用して、double 配列内の一意の各要素の出現回数をカウントできます。これは次のようになります。

  • 線形O(n)時間で実行し、
  • O(n)スペースが必要

疑似コードは次のようになります。

  • 配列のすべての要素を 1 回繰り返します: O(n)
    • 訪問した各要素について、そのキーがすでに HashMap に存在するかどうかを確認します: O(1), amortized
    • そうでない場合 (この要素を初めて見た場合)、[キー: この要素、値: 1] として HashMap に追加します。O(1)
    • 存在する場合は、キーに対応する値を 1 増やします。O(1)、償却済み
  • HashMap の構築が完了したら、マップを反復処理して、関連付けられた値が最も高いキーを見つけます。これが、出現回数が最も多い要素です。の上）

HashMap の使用方法を理解するための部分的なコード ソリューション:

import java.util.HashMap;
...

    HashMap hm = new HashMap();
    for (int i = 0; i < array.length; i++) {
        Double key = new Double(array[i]);
        if ( hm.containsKey(key) ) {
            value = hm.get(key);
            hm.put(key, value + 1);
        } else {
            hm.put(key, 1);
        }
    }

後で HashMap を反復処理して最大値のキーを見つける方法の演習として残します。しかし、行き詰まった場合は、別のコメントを追加してください。さらにヒントを得ることができます =)

于 2012-11-25T16:34:45.717 に答える
7

Collections.frequencyオプションを使用:

 List<String> list = Arrays.asList("1", "1","1","1","1","1","5","5","12","12","12","12","12","12","12","12","12","12","8");
      int max = 0;
      int curr = 0;
      String currKey =  null;
      Set<String> unique = new HashSet<String>(list);

          for (String key : unique) {
                curr = Collections.frequency(list, key);

               if(max < curr){
                 max = curr;
                 currKey = key;
                }
            }

          System.out.println("The number "  + currKey + " happens " + max + " times");

出力：

The number 12 happens 10 times

于 2012-11-25T16:42:17.157 に答える
5

別の方法を提案します。これがより速く機能するかどうかはわかりません。

配列をクイックソートします。組み込みの Arrays.sort() メソッドを使用します。

次に、隣接する要素を比較します。次の例を検討してください。

1 1 1 1 4 4 4 4 4 4 4 4 4 4 4 9 9 9 10 10 10 29 29 29 29 29 29

隣接する要素が等しくない場合、その要素のカウントを停止できます。

于 2012-11-25T16:43:49.457 に答える
-1

Rubyソリューションは次のとおりです。

def maxOccurence(arr)
  m_hash = arr.group_by(&:itself).transform_values(&:count)
  elem = 0, elem_count = 0
  m_hash.each do |k, v|
    if v > elem_count
        elem = k
        elem_count = v
    end
  end
  "#{elem} occured #{elem_count} times"
end

p maxOccurence(["1", "1","1","1","1","1","5","5","12","12","12","12","12","12","12","12","12","12","8"])

出力：

"12 occured 10 times"
于 2020-08-12T16:19:28.740 に答える