确定1到N范围内缺失值的常见访谈问题已经完成了一千次 . 变化包括2个缺失值，最多K个缺失值 .
示例问题：范围[1,10]（1 2 4 5 7 8 9 10）= {3,6}
以下是各种解决方案的示例：
Easy interview question got harder: given numbers 1..100, find the missing number(s)
我的问题是，看到一个缺失值的简单情况是O（n）复杂性，并且较大情况的复杂性收敛于大于O（nlogn）的大小：
通过对范围进行排序（mergesort）并迭代它来观察缺失的元素，难道只是更容易回答这个问题吗？
此解决方案不应超过 O(nlogn) ，并且能够解决1到N之外的范围的问题，例如10到1000或-100到100等...
是否有理由相信上述SO链接中的给定解决方案将比基于排序的解决方案更好地存在大量缺失值？
注意：对于这个问题，似乎有许多常见的解决方案，假设只有数论的方法 . 如果有人在S / E面试中被问到这样的问题，那么复杂性就不会......
更多相关链接：
6 回答
您只是指定时间复杂度，但空间复杂性也很重要 .
问题的复杂性可以用
N（范围的长度）和K（缺失的元素的数量）来指定 .在你链接的问题中，使用方程的解是空间中的O（K）（或者可能更多？），因为每个未知值需要一个方程 .
还有保存点：你可以改变已知元素的列表吗？在许多情况下，这是不合需要的，在这种情况下，任何涉及重新排序元素或消耗它们的解决方案必须首先在空间中制作O（N-K）副本 .
我看不到比线性解决方案更快的速度：您需要读取所有已知元素（N-K）并输出所有未知元素（K） . 因此，你不能及时比O（N）好 .
让我们分解解决方案
销毁，O（N）空间，O（N log N）时间：就地排序
保留，O（K）空间？，O（N log N）时间：方程系统
保留，O（N）空间，O（N）时间：计数排序
就个人而言，虽然我发现方程式系统解决方案很聪明，但我可能会使用其中一种排序解决方案 . 让我们面对现实：它们更容易编码，特别是计数排序！
而且就时间而言，在真正的执行中，我认为“计数排序”将击败所有其他解决方案 .
Note ：计数排序不要求范围为
[0, X)，任何范围都可以，因为任何有限范围都可以通过简单的转换转换为[0, X)形式 .EDIT ：
将排序更改为O（N），需要具有可用于排序它们的所有元素 .
我有一些时间来思考这个问题，我还有另一个解决方案 . 如上所述，当N（显着）增长时，所需的空间可能会爆炸 . 但是，如果K很小，那么我们可以使用间隔来更改列表的表示：
{4, 5, 3, 1, 7}可以表示为
[1,1] U [3,5] U [7,7]在一般情况下，维护一个排序的间隔列表比维护一个排序的元素列表要便宜得多，而且推断丢失的数字也很容易 .
时间复杂度很容易：O（N log N），毕竟它基本上是一个插入排序 .
当然，真正有趣的是没有必要实际存储列表，因此您可以使用流向算法提供它 .
另一方面，我很难搞清楚平均空间复杂度 . 占用的“最终”空间是O（K）（最多K 1个间隔），但在构造期间，由于我们不按特定顺序引入元素，因此会有更多的缺失间隔 .
最糟糕的情况很容易：N / 2个间隔（想想奇数和偶数） . 然而，我无法弄清楚平均情况 . 我的直觉告诉我它应该比O（N）更好，但我不是那么信任 .
因为数字来自一个小的有限范围，所以它们可以在线性时间内“排序” .
我们所做的只是初始化一个包含100个布尔值的数组，并为每个输入设置对应于输入中每个数字的布尔值，然后逐步报告未设置的布尔值 .
如果总共有 N 个元素，其中每个数字 x 都是 1 <= x <= N 那么我们可以在 O(nlogn) 时间复杂度和 O(1) 空间复杂度中解决这个问题 .
首先使用quicksort或mergesort对数组进行排序 .
扫描已排序的数组，如果先前扫描的数字，a和当前数字之间的差值b等于2（b - a = 2），则缺失的数字为1.这可以扩展到条件所在的位置（b - a> 2） .
当N> 100时，时间复杂度O（nlogn）O（n）几乎等于O（nlogn） .
理论上给定的解决方案是否更好而排序依赖于N和K.虽然您的解决方案具有
O(N*log(N))的复杂性，但给定的解决方案是O(N*K). 我认为给定的解决方案（与排序解决方案相同）能够通过将范围[A, B]转换为[1, N]来解决任何范围[A, B].如果向前提供了范围，在这种情况下范围是[1,10]，您可以使用您的范围和给您的数字执行XOR运算 . 由于XOR是可交换操作 . 你会留下{3,6}
（1 2 3 4 5 6 7 8 9 10）异或（1 2 4 5 7 8 9 10）= {3,6}
那这个呢？
创建包含所有数字的集合
从您的集合中删除给定的一组数字（无需排序）
您的设置中剩下的是丢失的数字 .