java - 用Java写一个mode方法找到数组中出现频率最高的元素

Question

问题是:

Write a method called mode that returns the most frequently occurring element of an array of integers. Assume that the array has at least one element and that every element in the array has a value between 0 and 100 inclusive. Break ties by choosing the lower value.

For example, if the array passed contains the values {27, 15, 15, 11, 27}, your method should return 15. (Hint: You may wish to look at the Tally program from earlier in this chapter to get an idea of how to solve this problem.)

下面是我的代码，除了单元素数组外几乎都可以工作

public static int mode(int[] n)
{
    Arrays.sort(n);
    
    int count2 = 0;
    int count1 = 0;
    int pupular1 =0;
    int popular2 =0;
    
    
    for (int i = 0; i < n.length; i++)
    {
            pupular1 = n[i];
            count1 = 0;    //see edit
        
        for (int j = i + 1; j < n.length; j++)
        {
            if (pupular1 == n[j]) count1++;
        }
        
        if (count1 > count2)
        {
                popular2 = pupular1;
                count2 = count1;
        }
        
        else if(count1 == count2)
        {
            popular2 = Math.min(popular2, pupular1);
        }
    }
    
    return popular2;
}

编辑:终于弄明白了。将 count1 = 0; 更改为 count1 = 1; 现在一切正常!

Answer 1

对于此类问题，您应该使用 HashMap 。将每个元素输入 hashmap 需要 O(n) 的时间，检索元素需要 o(1) 的时间。在给定的代码中，我基本上取了一个全局最大值并将它与从 hashmap 中“获取”时收到的值进行比较，每次我向其中输入一个元素时，看看:

hashmap有两部分，一是key，二是value，对key做get操作，返回的是value。

public static int mode(int []array)
{
    HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();
    int max  = 1;
    int temp = 0;

    for(int i = 0; i < array.length; i++) {

        if (hm.get(array[i]) != null) {

            int count = hm.get(array[i]);
            count++;
            hm.put(array[i], count);

            if(count > max) {
                max  = count;
                temp = array[i];
            }
        }

        else 
            hm.put(array[i],1);
    }
    return temp;
}