java - 计算和查找事件的有效方法(乐透分析)

Question

我想实现两件事: 1)从乐透结果中找出对号并存储到哈希表中。 2)以有效的方式循环乐透结果，计算频率并将频率结果添加到对号哈希表中。

我想构建一个能够告诉我配对号码频率的程序。

For a list / array of number , example :
    4, 12, 20 , 32, 48, 50
    2, 22, 20 , 32, 38, 40
    4, 12, 20 , 25, 33, 44
    1, 11, 20 , 31, 48, 50
    1, 12, 20 , 36, 47, 51

我想要的结果:

    Pair Number     |      Repeat Times
    4, 12                          2
    4, 20                          2
    12, 20                         3
      .                            .
      .                            .

列出所有可能的自动对数
列表/数组中不需要的数据。还有其他建议可以存储数据以便于分组吗？ map ？

除了循环之外，还有什么有效的方法可以对重复次数进行分组和计数？

感谢任何建议和建议。

Answer 1

为了清楚起见，假设您从 n 集合开始，这些集合由 c 元素(在本例中为数字)组成。您的问题是找到所有集合中大小为 2 的所有唯一子集的聚合频率(即跨越所有集合)。

为此，遍历每个集合并考虑该集合中的每一对元素，并在哈希表中维护其频率。当您考虑一对时，如果它已经存在于哈希表中，则将其值加 1；否则，将其添加到值为 1 的哈希表中。您的代码将类似于下面的伪代码。

hashtable h
for s in sets:
   for i in s.size():
       for j > i in s.size():
            pair p = (s[i],s[j])
            if h.exists(p):
                h[p]++
            else:
                h.put(p,1)

由于这种方法有一个限制为n、c 和c 的三重嵌套循环，因此该算法在O 中执行(nc^2) 时间。

考虑一个极端情况，其中每个可能的大小为 2 的子集都是唯一的。在这种情况下，您的频率表将包含 n × c choose 2 元素。在大 O 表示法中，此值减少为 O(nc^2)。因此，最好的解决方案不比O(nc^2)好，这正是上述算法的速度。