这个问题几乎在标题中，但是说我有一个列表 L
L = [1,2,3,4,5]
min(L) = 1 这里。现在我移除 4。最小值仍然是 1。然后我移除 2。最小值仍然是 1。然后我移除 1。最小值现在是 3。然后我移除 3。最小值现在是 5，依此类推。
我想知道是否有一种好方法可以随时跟踪列表的最小值，而无需执行 min(L) 或扫描整个列表等。
实际从列表中删除项目会产生效率成本，因为它必须将其他所有内容都移过来。每次重新排序列表也很昂贵。有没有解决的办法？
问问题
149 次
5 回答
6
要删除随机元素，您需要知道哪些元素尚未删除。
要知道最小元素，您需要对项目进行排序或扫描。
实现为数组的最小堆巧妙地解决了这两个问题。删除一个项目的成本是 O(log N)，找到最小值的成本是 O(1)。这些项目连续存储在一个数组中，因此随机选择一个非常容易，O(1)。
顺便说一句，如果数据很大，您可以将它们留在原处并将指针或索引存储在最小堆中并相应地调整比较运算符。
于 2013-07-22T16:49:05.533 回答
2
谷歌自平衡二叉搜索树。从初始列表构建一个需要 O(n lg n) 时间，查找和删除任意项目将花费 O(lg n)（而不是 O(n) 从简单列表中查找/删除）。最小的项目将始终出现在树的根部。
这个问题可能有用。它提供了各种平衡二叉搜索树的几种实现的链接。使用哈希表的建议不适用于您的情况，因为它没有解决维护最小项目的问题。
于 2013-07-22T16:41:06.497 回答
1
这是一个需要 O(N lg N) 预处理时间 + O(lg N) 更新时间和 O(lg(n)*lg(n)) 删除时间的解决方案。
预处理：
第 1 步：对 L 进行排序
第 2 步：对于每个项目 L[i]，映射 L[i]->i
第 3 步：构建一个二叉索引树或分段树，其中对于每个 1<=i<=L 的长度，BIT[i]=1 并保持范围之和。
查询类型删除：
第 1 步：如果项目 x 被删除，则对数组 L（其中 L 已排序）进行二分搜索或从映射中找到其索引。设置 BIT[index[x]] = 0 并更新所有范围。运行时：O(lg N)
查询类型 findMin：
第 1 步：对数组 L 进行二进制搜索。对于每个中间值，从 1-mid 找到 BIT 上的总和。如果 BIT[mid]>0 那么我们知道一些 value<=mid 仍然存在。所以我们设置 hi=mid-1。否则我们设置低=中+1。运行时间：O(lg**2N)
段树也可以这样做。
编辑：如果每个查询我没有错，可以使用链表在 O(1) 中处理
于 2013-07-22T17:09:24.000 回答
0
如果排序不符合您的最佳利益，我建议仅在需要进行比较时进行比较。如果您删除了不是旧最小值的元素，并且没有插入任何新元素，则不需要重新扫描最小值。
您能否向我们提供更多有关您正在尝试进行的处理的信息？
评论答案：您不必计算 min(L)。只需跟踪其索引，然后仅在删除旧索引处（或以下）时重新运行 min(L) 扫描（并确保相应地跟踪它）。
于 2013-07-22T16:38:26.997 回答
0
您当前在删除最小值时重新扫描的方法是每次删除的预期时间为 O(1) 时间（假设每个项目都同样可能被删除）。
给定 n 个项目的列表，重新扫描是必要的，概率为 1/n，因此每一步的预期工作是 n * 1/n = O(1)。
于 2013-07-22T18:15:21.340 回答