4

我想根据百分比选择卡片的顶部“范围”。我将所有可能的 2 张牌按照牌的强度排列成一个数组，如下所示：

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

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

Arrays.copyOfRange(cardArray, 0, 16);

然而，我现在意识到这是不正确的，因为有更多可能的组合，比如 Ace King 非同花 - 12 种组合（即一个花色的 A 和另一个花色的 K）比有一个组合，比如说，a一对 A - 6 种组合。

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

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

6, 12, 16, 22

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

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

我想知道是否有办法可以在恒定时间内做到这一点？

4

2 回答 2

3

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

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

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

于 2011-12-22T14:20:14.750 回答
1

在这里进行了类似的讨论Algorithm for pick up thumbed items作为对我的回答的评论（基本上你想用你的卡片列表做什么），有人建议了一个特定的数据结构，http ://en.wikipedia.org/wiki /Fenwick_tree

此外，请确保您的数据结构能够提供对前 5% 到 15% 之间的有效访问（虽然不是与编码相关的提示；）。

于 2011-12-23T18:49:12.843 回答