如何最有效地找到巴西Mega彩票的中奖者？

Question

大塞纳是巴西最著名的彩票。数字集的范围从1到60，单个打赌可以包含6到15个选择的数字(选择的数字越多，赌注就越昂贵)。按比例给那些能够正确猜出4、5或6个数字()的人()颁奖，后者是头奖。

有时，投注的总数达到了数亿。图画是电视直播的，所以作为一名玩家，你几乎可以即时知道你是否赢了。然而，彩票需要几个小时才能公布中奖者的数量和他们来自哪个城市。

考虑到上面的规则，您将如何实现找到赢家的计算逻辑？您会选择什么数据结构来存储数据？如果有的话，你会选择哪种排序算法？你能想到的最佳解决方案的大O表示法是什么？

Answer 1

我会分配一个64位整数来表示选择了哪些数字.

第一步是将所有7-15号票扩展到只有6位的票，这可以在绘图之前离线完成。我不知道15个号码的票是否包含所有(15选择6) = 5005 6元素的票，还是使用另一种系统。但是，由于它是脱机完成的，复杂性被委派到其他地方。

甚至还有一个算法(或bithack)，称为字典下置换，它能够高效地生成所有的k位模式，如果需要实时完成的话。

用获胜行的位模式屏蔽所有这些票，并计算剩馀位数。在一台拥有popcount指令的现代计算机中，这应该是非常有效的，在一台现代计算机中，每10亿张票就能订购1秒。

另一个问题是数据的有效性、完整性和保密性，当与票证持有者相关联时。我猜这才是真正的问题，可能是通过数据库查询实现整个过程来解决的。

Answer 2

您可以将每个人的选择保存在一个64位字内，每个位代表选定的数字。整个数据集可以存储在一个长整数数组中。

如果数组按照与数据库相同的顺序排序，例如，按票证ID排序，那么只需知道数组中的位置将与查询的行相同，就可以检索相关的记录。

如果您使用获胜数字的64位表示来按位执行每个值的操作，则可以计数这些位并将任何匹配的4、5或6位的偏移存储到各自的列表中。

整个操作很明显是线性的O(n)。