26 c++ math complexity-theory computer-science
确定1到N范围内缺失值的常见访谈问题已经完成了一千多次.变化包括2个缺失值,最多K个缺失值.
示例问题:范围[1,10](1 2 4 5 7 8 9 10)= {3,6}
以下是各种解决方案的示例:
简单的面试问题变得更难:给出数字1..100,找到丢失的数字
我的问题是,看到一个缺失值的简单情况是O(n)复杂性,并且较大情况的复杂性收敛于大于O(nlogn)的大小:
通过对范围进行排序(mergesort)并迭代它来观察缺失的元素,难道只是更容易回答这个问题吗？
该解决方案应该不超过O(nlogn),并且能够解决1到N之外的范围的问题,例如10到1000或-100到+100等......
是否有理由相信上述SO链接中的给定解决方案将比基于排序的解决方案更好地存在大量缺失值？
注意:对于这个问题,似乎有很多常见的解决方案,假设只有一个数论的方法.如果在S/E采访中被问到这样一个问题,使用更多的计算机科学/算法方法是不谨慎的,假设该方法与数论解决方案的复杂性相同......
更多相关链接:
Mat*_* M. 11
您只是指定时间复杂度,但空间复杂性也很重要.
可以根据N(范围的长度)和K(缺失元素的数量)来指定问题的复杂性.
在你链接的问题中,使用方程的解是空间中的O(K)(或者可能更多？),因为每个未知值需要一个方程.
还有保存点:你可以改变已知元素的列表吗？在许多情况下,这是不合需要的,在这种情况下,任何涉及重新排序元素或消耗元素的解决方案必须首先在空间中制作副本O(NK).
我看不到比线性解决方案更快的速度:你需要读取所有已知元素(NK)并输出所有未知元素(K).因此,你不能及时比O(N)好.
让我们分解解决方案
就个人而言,虽然我发现方程式系统解决方案很聪明,但我可能会使用其中一种排序解决方案.让我们面对现实吧:它们更容易编码,尤其是计数排序!
而且就时间而言,在真正的执行中,我认为"计数排序"将击败所有其他解决方案.
注意:计数排序不需要范围[0, X),任何范围都可以,因为任何有限范围都可以[0, X)通过简单的平移转换到表单.
编辑:
将排序更改为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 个布尔值的数组，并为每个输入设置与输入中每个数字对应的布尔值，然后逐步报告未设置的布尔值。