Mat*_* M. 5 algorithm combinatorics setinterval
在检查"找出该集合中的K缺失数据应该涵盖[0..N]"问题时,出现了这个问题.
该问题的作者要求CS答案而不是基于方程式的答案,他的建议是对输入进行排序,然后对其进行迭代以列出K缺失的数字.
虽然这对我来说似乎很好,但它似乎也很浪费.我们来举个例子:
"已排序"集合可以表示为:[0, 52] U [54, 74] U [76, 200],这比枚举集合的所有值(并允许在O(K)操作中检索缺失的数字)更紧凑,如果集合是O(N)则与O(N)进行比较排序).
然而,这是最终结果,但在构造期间,间隔列表可能会大得多,因为我们一次一个地提供元素....
因此,让我们引入另一个变量:I设为到目前为止我们提供给结构的集合的元素数量.然后,我们可能在最坏的情况下:min((N-K)/2, I)间隔(我认为...)
从中我们推断出在构造期间达到的间隔数是[0..N]中I遇到的最大值,因此最坏的情况就是(N-K)/2如此O(N).
我有一个但是感觉:如果输入的是随机的而不是特制的,我们可能会得到一个很大的下限......因而总是如此棘手的问题:
间隔多少......平均？
您的方法与建议的排序方法似乎是一种经典的权衡，即哪些操作便宜，哪些操作昂贵。
我发现你的符号有点混乱，所以请允许我使用我自己的：
让其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插入O(nlogn)+O(n)查找 k 个缺失的数字，因此总成本再次为O(nlogn)。
这并不比第一个算法的预期成本更好。
第三种解决方案是使用布尔值array来表示集合，并使用单个整数max表示集合中的最大元素。
如果将一个元素e添加到 Set 中，则设置array[e] = true。您可以使用表扩展来实现集合的可变大小，因此将元素插入数组的成本是恒定的。
要检索丢失的元素，您只需收集那些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并删除Sfrom中的每个元素R。
其成本也是O(n + k)。