c - 有效地选择一个与列表的所有元素不同的整数

Question

我有一个对象的链接列表，每个对象都包含一个 32 位整数(并且可以证明少于 2³² 个这样的对象)并且我想有效地选择一个列表中不存在的整数，< strong>不使用任何额外的存储空间(因此将它们复制到一个数组，对数组进行排序，并选择不在数组中的最小值将不是一个选项)。但是，列表元素的结构定义在我的控制之下，因此我可以(在合理范围内)为每个元素添加额外的存储作为解决问题的一部分。例如，我可以添加一组额外的上一个/下一个指针并对列表进行合并排序。这是最好的解决方案吗？或者有更简单或更有效的方法吗？

Answer 1

鉴于您在评论中概述的条件，尤其是您对许多相同值的期望，您必须期望使用值的稀疏分布。

因此，实际上最好只是随机猜测一个值，然后检查它是否与列表中的值一致。即使使用了可用值范围的一半(从您的评论来看这似乎极不可能)，您平均也只会遍历列表两次。您可以通过在一次通过中同时检查多个猜测来大大减少这个因素。如果操作得当，该因子应始终接近于 1。

这种概率方法的优点是您不会受到错误值序列的影响。这样的序列在基于范围的方法中总是可能的:如果你计算数据的最小值和最大值，你就有风险，数据同时包含0。和 2^32-1 .如果按顺序 segmentation 一个区间，则冒着总是在区间中间获取值的风险，这可能会在 32 个步骤中将其缩小为零。使用概率方法，这些序列不会伤害您。

我认为，对于非常小的列表，我会使用类似四次猜测的方法，并在列表的大小接近极限时将其增加到大约 16。高起始值是由于任何此类算法都将受内存限制，即。 e.在等待下一个值从内存到达时，您的 CPU 有足够的时间来检查一个值，因此您最好利用这段时间来减少所需的传递次数。

进一步的优化会立即用新的猜测替换失败的猜测，并跟踪替换发生的位置，这样您就可以避免完全第二次遍历数据。此外，将失败的猜测移动到猜测列表的末尾，这样您只需检查循环中第一个猜测的开始位置即可尽早停止。