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

Question

问题是：

编写一个名为 mode 的方法，返回整数数组中出现频率最高的元素。假设数组至少有一个元素，并且数组中的每个元素的值都在 0 到 100 之间（含 0 和 100）。通过选择较低的值来打破平局。

例如，如果传递的数组包含值 {27, 15, 15, 11, 27}，您的方法应该返回 15。（提示：您可能希望查看本章前面的 Tally 程序以了解如何解决这个问题呢。）

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

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; 现在一切正常！

原文由 TonyGW 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

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

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

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

原文由 codemania23 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

您应该能够在 N 次操作中执行此操作，这意味着只需一次，即 O(n) 时间。

使用 map 或 int[]（如果问题仅针对整数）来递增计数器，并使用一个变量来保存具有最大计数的键。每次增加计数器时，询问值是多少并将其与上次使用的密钥进行比较，如果值较大则更新密钥。

 public class Mode {
public static int mode(final int[] n) {
    int maxKey = 0;
    int maxCounts = 0;

    int[] counts = new int[n.length];

    for (int i=0; i < n.length; i++) {
        counts[n[i]]++;
        if (maxCounts < counts[n[i]]) {
            maxCounts = counts[n[i]];
            maxKey = n[i];
        }
    }
    return maxKey;
}

public static void main(String[] args) {
    int[] n = new int[] { 3,7,4,1,3,8,9,3,7,1 };
    System.out.println(mode(n));
}
}

原文由 Gubatron 发布，翻译遵循 CC BY-SA 3.0 许可协议