找到数组中出现次数最多的元素[java] [英] Find the element with highest occurrences in an array [java]

问题描述

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

I have to find the element with highest occurrences in a double array. I did it like this:

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

该程序有效，但速度太慢了！我必须找到一个更好的解决方案，任何人都可以帮助我吗？

The program works, but it is too slow! I have to find a better solution, can anyone help me?

推荐答案

更新：

• 正如Maxim指出的那样，使用 HashMap 比 Hashtable 此处。


• 这里的假设是您不关心并发性。如果需要同步访问，请使用 ConcurrentHashMap 代替。

• 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.

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

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

• 以线性 O（n）时间运行，


• 需要 O（n）空间

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

Psuedo代码会是什么东西像这样：

Psuedo code would be something like this:

• 迭代一次数组中的所有元素： O（n）
  
  
  
  • 对于访问过的每个元素，检查其密钥是否已存在于HashMap中： O（1），摊销
  
  
  • 如果没有（第一次看到这个元素），那么将它作为[key：this elemen]添加到你的HashMap中t，值：1]。 O（1）
  
  
  • 如果确实存在，则将与该键对应的值增加1. O（1），摊销
  
  
  • 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)
    • If it does exist, then increment the value corresponding to the key by 1. O(1), amortized

    部分代码解决方案给您一个想法如何使用HashMap：

    A partial code solution to give you an idea how to use 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找到具有最高值的密钥;但如果你遇到困难，只需添加另一条评论，我会给你更多提示=）

    I'll leave as an exercise for how to iterate through the HashMap afterwards to find the key with the highest value; but if you get stuck, just add another comment and I'll get you more hints =)

    这篇关于找到数组中出现次数最多的元素[java]的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！