假设我有一个可能较大的 32 位数字数组，可能有几百万个条目长...有没有一种方法可以有效地挑选一些没有出现在数组中任何地方的相同位宽的数字？天真地，我可以只选择一些适当宽度的随机数，然后检查数组，如果它出现在数组中，返回并选择另一个，但由于数组中元素的数量，可能需要重新扫描数组的成本反复令人担忧。在实践中，我不确定这会有多大问题，因为可能永远不会超过 2000 万个条目，而唯一值的数量是几十亿，所以可能需要重新扫描的总体可能性该数组将很少发生，因此这不是问题。尽管如此，这种算法可能会多次重复重新扫描数组这一事实对我来说很麻烦，如果能找到更好的解决方案，我理想情况下会喜欢。从技术上讲，数字甚至不必是随机的...确定性值是可以接受的，唯一的要求是生成的数字必须是唯一的，并且尚未出现在列表中。
那么...是否有一种运行时有效的方法来生成唯一数字，或者我上面描述的随机数方法是唯一可行的方法吗？关于时间/空间权衡，我对速度更感兴趣，因此保证 O(n) 算法是理想的，但我可能不希望任何额外的空间需求大于大约 O(n log n)。
这最终将在 C 中实现，但可以接受任何语言中性术语的算法描述。
最佳答案
扫描大型数组的大部分成本都在内存访问中。您可以通过选择一小组候选随机数来大大降低重新扫描的风险。
在扫描期间，将集合中的每个成员与当前数组元素进行比较。如果匹配则删除集合成员。如果这使得集合变空，则您必须返回并重新开始一个新集合。如果您以非空候选集结束，请选择任何幸存的成员。
关于arrays - 有效地挑选一个唯一的号码，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28303643/