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;
  }
}

或者你可能喜欢番石榴的Mulitset

Answer 3

是的，慢慢来。

您可以使用列表列表来执行此操作；内部列表包含您看到的数字，外部列表的索引是出现次数。所以在处理“1,2,1,3,1,2,3,4”之后你会有

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

处理完输入列表后，您可以获得外部列表的最高索引包含的最后一个内部列表，在本例中为[1]. 该列表中的所有元素都与最大出现次数相关联。

Answer 4

这里有两个不同复杂度的简单实现（当然，如果你只有几个数字，性能提升是象征性的）：

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));
    }
}