我可以比二进制搜索做得更好吗？

我想根据百分比挑选卡片的顶部“范围”。我有我的所有可能的2手牌在手的实力的顺序在阵列组织，就像这样：我可以比二进制搜索做得更好吗？

AA, KK, AKsuited, QQ, AKoff-suit ...

我是已通过该卡数组的长度乘以采摘手的前10％这个百分比会给我数组中最后一张牌的索引。然后，我只想让子数组的副本：

Arrays.copyOfRange(cardArray, 0, 16);

不过，我现在认识到，因为有，比如说，王牌敬客，西装更可能的组合，这是不正确 - 12个组合（即一套西装的王牌和另一套西装的国王）比组合，比如说，一对王牌 - 6种组合。

当我拿起手中的前10％，因此，我希望它可以根据手的前10％的比例的2个卡组合的总数 - 52选2 = 1326

我想我可以有一个整数数组，其中每个索引都保存了到该点为止的所有组合的总数（每个索引将对应于原始数组中的一只手）。因此，阵列的前几个指数将是：

6, 12, 16, 22

因为有AA的6种组合，KK的6种组合，AKsuited的4种组合，QQ的6种组合。

然后我可以做一个二进制搜索，它运行在BigOh（log n）时间。换句话说，我可以将组合的总数（1326）乘以百分比，搜索第一个低于或等于该数字的索引，并且这将是我需要的原始数组的索引。

我想知道是否有一种方法可以在常量时间内完成此操作？

来源

2011-12-22 Joe

由于1326不是那么大的数字，为什么不简单地预先创建所有的元组并将它们存储在一个有序数组中呢？ – Groo 2011-12-22 14:06:57

你的意思是说我有一个长度为1326的二维数组，在另一个维度中，它会有一个卡片范围数组？因此，第一个索引将有一个“AA”阵列，最后一个索引将包含一个包含所有可能手的数组。这个数据结构通常如何在软件中初始化？我使用Java，所以我可以将它作为文字键入 - NO，在构造函数中以编程方式构造，并确保将该对象保持为活动状态，因此我只需要执行一次，或者从文件中读取该计划的开始。谢谢你的评论。 – Joe 2011-12-22 14:29:08

我正在考虑按顺序排序的* all *组合的1维数组。从52张牌组中选择两张牌有1326种方式，因此只需创建所有组合并对其进行分类。 – Groo 2011-12-22 14:36:05

正如Groo建议的那样，如果预计算和内存开销允许，创建6个AA副本，6个KK副本等等并将它们存储到排序数组中将会更有效。然后你可以在这个适当加权的列表上运行你的原始算法。

如果查询数量很大，这是最好的。

否则，我不认为你可以实现每个查询的恒定时间。这是因为查询取决于整个频率分布。你不能仅仅关注元素的数量并确定它是否是正确的百分点。

来源

2011-12-22 14:20:14 tskuzzy

感谢您的回答。对，我认为Groo意味着有一个二维数组，因为我在他的评论下评论过。如果我使用1d解决方案，那么结果是我有问题的答案，这个范围内最差的手是什么，但我仍然必须找出原始数组中的位置（最坏的情况是BigOh（n）因为它没有排序），所以我可以指定方法的参数来获取子数组。但我很可能会错过一些东西。 – Joe 2011-12-22 14:33:40

这里Algorithm for picking thumbed-up items有过类似的讨论，至于我的回答（基本上你想与你的卡列表做什么），有人提出了一个具体的数据结构的评论，http://en.wikipedia.org/wiki/Fenwick_tree

此外，请确保您的数据结构能够提供有效的访问，例如，最高5％和15％之间的范围（尽管如此，不是编码相关的提示）。

来源

2011-12-23 18:49:12 Nicolas78

我可以比二进制搜索做得更好吗？

回答

相关问题