2

在Java中，我需要一个算法来找到最大值。整数集合中出现的次数。例如，如果我的集合是[2,4,3,2,2,1,4,2,2]，则算法需要输出 5，因为 2 是出现次数最多的整数，它出现了 5 次。把它想象成找到一组整数的直方图的峰值。

挑战是，我必须对多组许多整数一一进行，因此它需要高效。另外，我不知道哪个元素将主要出现在集合中。这是完全随机的。

我考虑过将集合的这些值放入一个数组中，对其进行排序，然后遍历数组，计算数字的连续出现并确定计数的最大值，但我猜这将花费大量时间。是否有任何库或算法可以帮助我有效地做到这一点？

4

7 回答 7

3

我将使用以下逻辑循环插入到 Map 数据结构中的集合：

  • 如果整数尚未插入映射，则插入 key=integer, value=1。
  • 如果键存在，则增加值。

您可以使用 Java 中的两个 Map - HashMap 和 TreeMap - 它们在下面进行比较：

HashMap 与 TreeMap

如果您愿意，您可以跳过详细说明直接跳转到摘要。

HashMap 是一种将键值对存储在数组中的 Map。用于键 k 的索引是：

  • h.hashCode() % map.size()

有时，两个完全不同的键最终会出现在同一个索引处。为了解决这个问题，数组中的每个位置实际上都是一个链表，这意味着每次查找都必须遍历链表并使用 k.equals(other) 方法检查是否相等。最坏的情况是，所有的键都存储在同一个位置，HashMap 变成了一个未索引的列表。

随着 HashMap 获得更多条目，这些冲突的可能性增加，并且结构的效率降低。为了解决这个问题，当条目数达到临界点（由构造函数中的 loadFactor 参数确定）时，会调整结构的大小：

  • 分配一个新数组，大约是当前大小的两倍
  • 在所有现有键上运行一个循环
    • 为新数组重新计算密钥的位置
    • 键值对插入到新结构中

如您所见，如果有很多调整大小，这可能会变得相对昂贵。

如果您可以在开始之前以适当的大小预先分配 HashMap，则可以克服此问题，例如 map = new HashMap(input.size()*1.5)。对于大型数据集，这可以显着减少内存流失。

因为键在 HashMap 中基本上是随机定位的，所以键迭代器将以随机顺序遍历它们。Java 确实提供了 LinkedHashMap，它将按照插入键的顺序进行迭代。

HashMap 的性能：

  • 给定正确的大小和良好的散列分布，查找是恒定时间的。
  • 如果分布不好，性能下降到（在最坏的情况下）线性搜索 - O(n)。
  • 如果初始大小不好，性能就会变成重新散列的性能。我不能简单地计算这个，但这并不好。

OTOH TreeMap 将条目存储在平衡树中 - 一种动态结构，随着键值对的添加而逐渐建立。插入取决于树的深度 (log(tree.size())，但可以预测 - 与 HashMap 不同，没有中断，也没有性能下降的边缘条件。

给定分布良好的 HashMap，每次插入和查找的成本都更高。

此外，为了在树中插入键，每个键都必须与其他所有键可比较，这需要 Comparable 接口中的 k.compare(other) 方法。显然，鉴于问题是关于整数的，这不是问题。

TreeMap 的性能：

  • 插入 n 个元素是 O(n log n)
  • 查找是 O(log n)

概括

第一个想法：数据集大小：

  • 如果很小（即使在 1000 和 10,000 中），在任何现代硬件上都无关紧要
  • 如果大到导致机器内存不足的地步，那么 TreeMap 可能是唯一的选择
  • 否则，大小可能不是决定因素

在这种特定情况下，一个关键因素是与整体数据集大小相比，唯一整数的预期数量是大还是小？

  • 如果很小，那么整体时间将由小集合中的键查找主导，因此优化无关紧要（您可以在这里停止）。
  • 如果很大，那么总时间将由insert控制，并且决定取决于更多因素：
    • 数据集大小已知？
      • 如果是：可以预先分配 HashMap，从而消除内存流失。如果 hashCode() 方法很昂贵（在我们的例子中不是），这一点尤其重要
      • 如果否：TreeMap 提供更可预测的性能，可能是更好的选择
    • 是否需要无需大停顿的可预测性能，例如在实时系统中或在 GUI 的事件线程上？
      • 如果是：TreeMap 提供了更好的可预测性，没有停顿
      • 如果否：HashMap 可能为整个计算提供更好的整体性能

最后一点，如果上面没有压倒性的一点：

  • 是一个排序的值键列表吗？
    • 如果是（例如打印直方图）：TreeMap 已经对键进行了排序，因此很方便

但是，如果性能很重要，那么唯一的决定方法是实现 Map 接口，然后分析HashMap 和 TreeMap 以查看在您的情况下哪个实际上更好。过早的优化是万恶之源 :)

于 2012-05-21T01:40:28.490 回答
3

排序有什么问题？那是O(n log n)，一点也不差。任何更好的解决方案要么需要有关输入集的更多信息（可能是所涉及数字的上限），要么涉及 aMap<Integer, Integer>或等效的东西。

于 2012-05-21T01:37:35.857 回答
2

  1. 基本方法是对集合进行排序，然后简单地运行排序后的集合。（这将在 O(nLog(n) + n) 中完成，即 O(nLog(n))）。

  2. 如果数字是有界的（例如，-10000,10000）并且集合包含很多整数，您可以使用查找表并计算每个元素。这将花费 O(n + l)（O(n) 进行计数，O(l) 找到最大元素）其中 l 是范围长度（在这种情况下为 20001）。正如你所看到的，如果 n >> l 那么这将变成 O(n) ，它比 1 更好，但是如果 n << l 那么它是 O(l) ，它是恒定的，但足够大以至于无法使用。

  3. 前面的另一个变体是使用 HashTable 而不是查找表。这会将复杂度提高到 O(n)，但不能保证在 n>>l 时比 2 快。好消息是这些值不必有界。

我不是一个java，但如果你需要帮助编码这些，让我知道。

于 2012-05-21T01:38:02.497 回答
1

由于它是整数的集合，因此可以使用

  1. 基数排序对集合进行排序，它采用 O(nb) 其中 b 是用于表示整数的位数（32 或 64，如果您使用 java 的原始整数数据类型），或者
  2. 基于比较的排序（快速排序、合并排序等），需要 O(n log n)。

笔记：

  • n 越大，基数排序就越有可能比基于比较的排序更快。对于较小的 n，您可能最好使用基于比较的排序。
  • 如果您知道集合中值的界限，则 b 将甚至小于 32（或 64），从而使基数排序更可取。
于 2012-05-21T04:39:54.240 回答
1

这是您的程序的示例实现。它返回频率最高的否，如果找到两个出现次数最多的否，则返回较大的否。如果您想返回频率，请将代码的最后一行更改为“返回 mf”。

{public int mode(int[]a,int n)
   {int i,j,f,mf=0,mv=a[0];
    for(i=0;i<n;i++)
       {f=0;
        for(j=0;j<n;j++)
           {if(a[i]==a[j])
               {f++;
               }
           }
        if(f>mf||f==mf && a[i]>mv)
           {mf=f;
            mv=a[i];
           }
       }
    return mv;        
   }

}

于 2012-05-21T04:03:39.980 回答
1

这只小狗工作（编辑返回频率而不是数字）：

public static int mostFrequent(int[] numbers) {
    Map<Integer, AtomicInteger> map = new HashMap<Integer, AtomicInteger>() {
        public AtomicInteger get(Object key) {
            AtomicInteger value = super.get(key);
            if (value == null) {
                value = new AtomicInteger();
                super.put((Integer) key, value);
            }
            return value;
        }

    };

    for (int number : numbers)
        map.get(number).incrementAndGet();

    List<Entry<Integer, AtomicInteger>> entries = new ArrayList<Map.Entry<Integer, AtomicInteger>>(map.entrySet());
    Collections.sort(entries, new Comparator<Entry<Integer, AtomicInteger>>() {
        @Override
        public int compare(Entry<Integer, AtomicInteger> o1, Entry<Integer, AtomicInteger> o2) {
            return o2.getValue().get() - o1.getValue().get();
        }
    });

    return entries.get(0).getValue().get(); // return the largest *frequency*

    // Use this next line instead to return the most frequent *number*
    // return entries.get(0).getKey(); 
}

选择 AtomicInteger 是为了避免在每次增量时创建新对象，并且代码读起来更简洁。

匿名地图类用于集中“if null”代码

这是一个测试：

public static void main(String[] args) {
    System.out.println(mostFrequent(new int[] { 2, 4, 3, 2, 2, 1, 4, 2, 2 }));
}

输出：

5
于 2012-05-21T04:12:05.433 回答
0

使用哈希映射：

  import java.util.HashMap;
public class NumberCounter {

   static    HashMap<Integer,Integer> map;
   static int[] arr = {1, 2, 1, 23, 4, 5, 4, 1, 2, 3, 12, 23};
   static int max=0;

   public NumberCounter(){


         map=new HashMap<Integer, Integer>();

    }

    public static void main (String[] args)
    {
        Integer newValue=1;
        NumberCounter c=new NumberCounter();

        for(int i=0;i<arr.length;i++){
            if(map.get(arr[i])!=null) {
                newValue = map.get(arr[i]);
                newValue += 1;
                map.put(arr[i], newValue);
            }
            else
                map.put(arr[i],1);


        }

        max=map.get(arr[0]);
        for(int i=0;i<map.size();i++){
         if(max<map.get(arr[i]))
             max=map.get(arr[i]);
        }
        System.out.print(max);

    }

}
于 2018-07-29T12:29:38.603 回答