c++ - 生成不同于数组的 1000 个元素的新元素

Question

我在一次采访中被问到这个问题。考虑穿孔卡片的场景，其中每张穿孔卡片都有 64 位模式。我被建议将每张卡片作为 int，因为每个 int 都是位的集合。

此外，考虑到我有一个数组，其中已经包含 1000 张这样的卡片。我每次都必须生成一个新元素，这与之前的 1000 张卡片不同。数组中的整数(又名卡片)不一定排序。

更重要的是，这怎么可能是 C++ 的问题，64 位 int 从哪里来，我如何从要生成的元素所在的数组中生成这张新卡片不同于数组中已经存在的所有元素？

Answer 1

有 2⁶⁴ 个 64 位整数，一个数太多了大于 1000，最简单的解决方案是只生成一个随机 64 位数字，然后验证它不在表中已经生成的数字。 (它是的概率是无穷小，但你不妨确定一下。)

由于大多数随机数生成器不生成 64 位值，因此您剩下的要么自己写，要么(更简单)结合值，比如生成 8 个随机字节，然后将它们 memcpyuint64_t。

至于验证数字是否已经存在，std::find 是适合一两个新号码；如果你必须做很多查找，对表进行排序并使用二进制搜索将是值得。或者某种哈希表。