java - ArrayList - 最も一般的な整数の検索

Question

私のarrayListには999個の数字があり、一部の数字は繰り返されています。そして、リストで最も頻度の高い番号を見つけたいのですが、それを行う最も効率的な方法は何ですか?

Answer 1

リストをソートし、ソートされたリストを読み取って、最も多く発生するカウントよりもカウントします。

0(n log n)時間必要

1 3 6 1 82 42 11 42 1 42 3 42

ソートされた

1 1 1 3 3 6 11 42 42 42 42 82

リストを左から右に読んで、これまでに最も多く見られた値とその頻度を覚えておいてください

Answer 2

コメントで書いたように
、テキストファイルから0から100までの数字を読んでいると思いますので、

int[] count = new int[101];
...
count[numberJustRead]++;
...

そしてすべての数字を読んだ後

int max = 0;
int maxIndex = 0; //this is what you looking for
for(int i = 0, k = count.length; i < k; i++){
  if(count[i] > max){
    max = count[i];
    maxIndex = i;
  }
}

またはあなたはおそらくグアバのマルチセットが好きです

Answer 3

複雑さが異なる2つの単純な実装を次に示します（もちろん、数値が少ない場合は、パフォーマンスの向上が象徴的です）。

import java.util.*;

public class Test
{
    static AbstractMap.SimpleEntry<Integer, Integer> getMostFrequentN2(ArrayList<Integer> values)
    {
        ArrayList<AbstractMap.SimpleEntry<Integer, Integer>> frequencies = new ArrayList<>();

        int maxIndex = 0;

        main:
        for (int i = 0; i < values.size(); ++i)
        {
            int value = values.get(i);

            for (int j = 0; j < frequencies.size(); ++j)
            {
                if (frequencies.get(j).getKey() == value)
                {
                    frequencies.get(j).setValue(frequencies.get(j).getValue() + 1);

                    if (frequencies.get(maxIndex).getValue() < frequencies.get(j).getValue())
                    {
                        maxIndex = j;
                    }

                    continue main;
                }
            }

            frequencies.add(new AbstractMap.SimpleEntry<Integer, Integer>(value, 1));
        }

        return frequencies.get(maxIndex);
    }

    static AbstractMap.SimpleEntry<Integer, Integer> getMostFrequentNLogN(ArrayList<Integer> values)
    {
        ArrayList<Integer> tmp = new ArrayList(values);

        Collections.sort(tmp);

        AbstractMap.SimpleEntry<Integer, Integer> max = new AbstractMap.SimpleEntry<>(0, 0);

        int current = tmp.get(0);
        int count = 0;
        for (int i = 0; i < tmp.size(); ++i)
        {
            if (tmp.get(i) == current)
            {
                count++;
            }
            else
            {
                if (count > max.getValue())
                {
                    max = new AbstractMap.SimpleEntry<Integer, Integer>(current, count); 
                }

                current = tmp.get(i);

                count = 1;
            }
        }

        if (count > max.getValue())
        {
            max = new AbstractMap.SimpleEntry<Integer, Integer>(current, count); 
        }

        return max;
    }

    public static void main(String[] args)
    {
        ArrayList<Integer> numbers = new ArrayList(99);

        for (int i = 0; i < 99; ++i)
        {
            numbers.add((int)(Math.random() * 10));
        }

        System.out.println(numbers);

        System.out.println(getMostFrequentN2(numbers));
        System.out.println(getMostFrequentNLogN(numbers));
    }
}

Answer 4

はい、ゆっくり。

リストのリストでこれを行うことができます。内側のリストにはあなたが見た数字が含まれており、外側のリストのインデックスは出現回数です。したがって、「1,2,1,3,1,2,3,4」を処理すると、

[ [4], [2, 3], [1] ]

入力リストの処理が完了すると、外側のリストの最高のインデックス (この場合は ) に含まれる最後の内側のリストを取得できます[1]。そのリスト内のすべての要素は、最大出現回数に関連付けられています。