找到数组中出现次数最多的元素[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;
 }

该程序有效,但太慢了!我必须找到更好的解决方案,任何人都可以帮助我吗？

Answer 1

Update:

• As Maxim pointed out, using HashMap would be a more appropriate choice than Hashtable here.
• The assumption here is that you are not concerned with concurrency. If synchronized access is needed, use ConcurrentHashMap instead.

You can use a HashMap to count the occurrences of each unique element in your double array, and that would:

• Run in linear O(n) time, and
• Require O(n) space

Psuedo code would be something like this:

• Iterate through all of the elements of your array once: O(n)
  • For each element visited, check to see if its key already exists in the HashMap: O(1), amortized
  • If it does not (first time seeing this element), then add it to your HashMap as [key: this element, value: 1]. O(1)
  • 如果确实存在,则将对应于该键的值递增1. O(1),摊销
• 完成构建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以找到具有最高值的键; 但如果你遇到困难,只需添加另一条评论,我会给你更多提示=)

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

Answer 3

我会建议另一种方法.我不知道这是否会更快.

快速排序数组.使用内置的Arrays.sort()方法.

现在比较相邻的元素.考虑这个例子:

1 1 1 1 4 4 4 4 4 4 4 4 4 4 4 4 9 9 9 10 10 10 29 29 29 29 29 29

当相邻元素不相等时,您可以停止计算该元素.

Answer 4

Java 8 的解决方案

       int result = Arrays.stream(array)
           .boxed()
           .collect(Collectors.groupingBy(i->i,Collectors.counting()))
           .values()
           .stream()
           .max(Comparator.comparingLong(i->i))
           .orElseThrow(RuntimeException::new));