algorithm - 0..N 中输入的平均间隔数

Question

在检查“在这个集合中找到应该覆盖 [0..N] 的 K 个缺失数字”问题时，这个问题就出现了。

该问题的作者要求 CS 答案而不是基于方程的答案，他的建议是对输入进行排序，然后对其进行迭代以列出 K 个缺失的数字。

虽然这对我来说似乎很好，但它似乎也很浪费。让我们举个例子:

N = 200

K = 2(我们将考虑 K << N)

缺失元素:53, 75

“排序”集可以表示为: [0, 52] U [54, 74] U [76, 200] ，这比枚举集合的所有值更紧凑(并且允许在 O(K) 操作中检索丢失的数字，如果集合已排序，则与 O(N) 进行比较)。

然而，这是最终结果，但在构建期间，间隔列表可能要大得多，因为我们一次提供一个元素......

因此，让我们引入另一个变量:让 I是到目前为止我们提供给结构的集合元素的数量。那么，我们最坏的情况可能是: min((N-K)/2, I)间隔(我认为...)

从中我们推断出在构造过程中达到的区间数是[0..N]中I遇到的最大值，最坏的情况是 (N-K)/2因此 O(N) .

然而，我有一种直觉，如果输入是随机的，而不是特制的，我们可能会得到一个更低的界限……因此这个问题总是那么棘手:

平均间隔是多少？

Answer 1

您的方法与建议的排序方法似乎是一种经典的权衡，即哪些操作便宜，哪些操作昂贵。

我发现你的符号有点困惑，所以请允许我使用我自己的:

让 S成为集合。让 n是集合中的项目数:n = |S| .让 max成为集合中最大的数:max = max(S) .让 k是不在集合中的元素数:k = |{0,...,max} \ S| .

对于排序解决方案，我们可以非常便宜地插入所有 n元素变成 S使用散列。这将需要预期 O(n) .然后寻找k缺少元素，我们在 O(nlogn) 中对集合进行排序，然后确定 O(n) 中的缺失元素.

即添加n的总成本元素，然后找到丢失的 k元素需要预期 O(n) + O(nlogn) + O(n) = O(nlogn) .

您建议采用不同的方法，将集合表示为 S 的密集子集列表。 .您将如何实现这样的数据结构？我建议使用排序树(而不是列表)，以便插入变得高效。因为插入新元素需要做什么e ?我认为你必须:

在树中找到潜在的候选子集​​，其中 e可以添加

如果子集已经包含 e ，什么都不用做。

如果子集包含 e+1另一个子集包含 e-1 ，将子集合并在一起并添加 e结果

如果子集已经包含 e+1 ，但是 e-1不包含在 S 中, 添加 e到该子集

如果子集已经包含 e-1 ，但是 e+1不包含在 S 中, 添加 e到该子集

否则，创建一个仅包含元素 e 的新子集并将其插入树中。

我们可以期望找到上述操作所需的子集需要 O(logn) .如果我们将子集表示为整数对(我们只需要减少下边界或增加上边界)，则 4. 或 5. 的操作需要恒定的时间。 3. 和 6. 可能需要更改树结构，但我们预计最多需要 O(logn) ，所以整个“插入”不会超过 O(logn) .

现在有了这样一个数据结构，我们可以很容易地确定 k通过按顺序遍历树并收集不在任何子集中的数字来丢失数字。成本与树中的节点数呈线性关系，即 <= n/2 ，所以总成本为 O(n)为了那个原因。

然而，如果我们再次考虑完整的序列操作，我们得到 n Blade O(nlogn) + O(n)用于查找 k 个缺失的数字，因此总成本再次为 O(nlogn) .

这并不比第一个算法的预期成本好。

第三种解决方案是使用 bool 值 array表示集合和单个整数 max为集合中最大的元素。

如果一个元素 e添加到 Set，您设置 array[e] = true .您可以使用 table expansion 实现集合的可变大小，因此将元素插入数组的成本是恒定的。

要检索丢失的元素，您只需收集这些元素 f哪里 array[f] == false .这需要 O(max) .

因此，插入 n 个元素并找到 k 个缺失元素的总成本为: O(n) + O(max) .然而， max = n + k ，所以我们得到总成本 O(n + k) .

第四种方法是第三种方法和使用散列的方法之间的交叉是以下方法，它也使用散列，但不需要排序。

存放您的套装 S在散列集中，并将最大元素存储在 S 中在一个变量 max .找到 k缺失的，首先生成一个包含所有数字的结果集R {0,...,max} .然后迭代 S并删除 S 中的每个元素来自 R .

费用也是 O(n + k) .