查找数组中出现次数最多的元素\[java\]

Question

我必须在双数组中找到出现次数最多的元素。我是这样做的：

 int max = 0;
for (int i = 0; i < array.length; i++) {
       int count = 0;
       for (int j = 0; j < array.length; j++) {
         if (array[i]==array[j])
             count++;
   }
  if (count >= max)
      max = count;
 }

该程序可以运行，但它太慢了！我必须找到更好的解决方案，有人可以帮助我吗？

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

Answer 1

更新：

• 正如 Maxim 指出的那样，在这里使用 HashMap 将是比 Hashtable 更合适的选择。
• 这里的假设是您不关心并发性。如果需要同步访问，请改用 ConcurrentHashMap 。

---

您可以使用 HashMap 来计算双精度数组中每个唯一元素的出现次数，这将：

• 以线性 O(n) 时间运行，并且
• 需要 O(n) 空间

伪代码 将是这样的：

• 遍历数组的所有元素一次： O(n)
  • 对于访问的每个元素，检查其键是否已存在于 HashMap 中： O(1)，已摊销
  • 如果没有（第一次看到这个元素），那么将它作为 [key: this element, value: 1] 添加到你的 HashMap 中。 O(1)
  • 如果确实存在，则将key对应的值加 1。O(1), amortized
• 完成构建 HashMap 后，遍历映射并找到具有最高关联值的键 - 这是出现次数最多的元素。 上）

部分代码解决方案，让您了解如何使用 HashMap：

 import java.util.HashMap;
...

    HashMap hm = new HashMap();
    for (int i = 0; i < array.length; i++) {
        Double key = new Double(array[i]);
        if ( hm.containsKey(key) ) {
            value = hm.get(key);
            hm.put(key, value + 1);
        } else {
            hm.put(key, 1);
        }
    }

我将留下一个练习，说明如何在之后遍历 HashMap 以找到具有最高值的键；但如果你遇到困难，只需添加另一条评论，我会给你更多提示 =)

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

Answer 2

使用 Collections.frequency 选项：

  List<String> list = Arrays.asList("1", "1","1","1","1","1","5","5","12","12","12","12","12","12","12","12","12","12","8");
      int max = 0;
      int curr = 0;
      String currKey =  null;
      Set<String> unique = new HashSet<String>(list);

          for (String key : unique) {
                curr = Collections.frequency(list, key);

               if(max < curr){
                 max = curr;
                 currKey = key;
                }
            }

          System.out.println("The number "  + currKey + " happens " + max + " times");

输出：

The number 12 happens 10 times

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