algorithm - 我可以在这里做得比二进制搜索更好吗？

Question

我想根据百分比选择最高“范围”的卡片。我将所有可能的 2 张牌按照手牌的强度排列在一个数组中，如下所示:

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

我一直在通过将卡片数组的长度乘以给出数组中最后一张卡片的索引的百分比来挑选前 10% 的牌。然后我只复制子数组:

Arrays.copyOfRange(cardArray, 0, 16);

但是，我现在意识到这是不正确的，因为有更多可能的组合，例如 Ace King off-suit - 12 种组合(即一种花色的 A 和另一种花色的 K)的组合，例如，一对 A - 6 种组合。

当我选择前 10% 的手牌时，我希望它基于前 10% 的手牌与 2 张牌组合总数的比例 - 52 选择 2 = 1326。

我想我可以有一个整数数组，其中每个索引保存到该点的所有组合的总和(每个索引对应于原始数组中的一只手)。所以数组的前几个索引是:

6, 12, 16, 22

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

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

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

Answer 1

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

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

否则，我认为您无法为每个查询实现恒定时间。这是因为查询依赖于整个频率分布。您不能只查看固定数量的元素并确定它是否是正确的百分位数。