algorithm - 列表中大于给定整数的整数数量可能不在日志日志时间列表中

Question

给定一个由 n 个非负整数组成的无序列表(不保证分布或重复)，我希望能够给出一个可能不在列表中的整数，并以至少与列表中一样大的整数作为响应在列表中。我有多达 n^2 的预处理时间，以及多达 n*log(n) 的存储空间。这可能吗？

我的不够好解决方案是二进制搜索(log n 时间，常量空间)。

在 map 中存储所有可能查询的 map 会占用太多存储空间。

编辑:需要对输入进行一些假设(例如整数的分布或最大大小)的部分解决方案也很有用。

编辑:这被称为前任/后继问题。 Beame＆Fich在一篇论文中构建了一个数据结构，该数据结构在 O(n) 空间中存储大小为 N 的宇宙中的 n 个整数元素集，并在 O(min{(log log N)/(log log log N), sqrt(log n/(log log n))}) 时间。

http://homes.cs.washington.edu/~beame/papers/stocpred.pdf

编辑 - 赏金:截至今天早上，没有一个答案正是我要找的。 N 不受限制。整数不一定低于 32 位。最大的元素可能远大于元素的数量。我假设输入没有分配。在现有的答案中，我接受了 Coffin 的赏金，因为它涵盖了我确实有分布的相对较大的问题子集。

Answer 1

假设您的元素分布相当均匀(或者至少相当接近地遵循一些分布)，显而易见的方法是对数据进行排序，然后使用插值搜索而不是二分搜索。

内插搜索通常具有大致 O(log log n) 的复杂度。

哦，如果从名字上看不太明显，插值搜索的基本思想是使用插值来猜测您要搜索的元素的大概位置。例如，如果您要处理 0 到 100,000 之间的整数，并且您需要找到 21,000，您可以从数组中大约 21% 的位置开始，而不是从中点开始。然后，根据您在那里找到的值，您可以使用插值法找到更好的猜测，等等。

该示例适用于线性插值，但相同的基本思想也适用于其他分布——您只需要使用适合(相当好地)数据分布的函数即可。