ArrayList的 - 寻找最常见的整数 [英] ArrayList - searching for the most common integer

问题描述

我有999号在我的ArrayList中，一些数字被重复。我想在列表中找到最频繁的号码，什么是这样做的最有效方法是什么？

I have 999 numbers in my arrayList, some of the numbers are repeated. And i want to find the most frequent number in the list, what is the most efficient way of doing that?

推荐答案

下面是具有不同的复杂性两个简单的实现（当然，如果你只有几个数字的性能增益是象征性的）：

Here are two simple implementations with different complexity (of course if you have only a few numbers performance gain is symbolic) :

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

这篇关于ArrayList的 - 寻找最常见的整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！