在列表中查找缺失项目的算法,哪个最快？

Question

所以我有一个非常简单的问题.我有一个数字列表1-N(迭代1),列表中的一个数字丢失.我试图确定我的两个解决方案中的哪一个在Big-Oh方面更快.

第一种算法:对列表进行排序,然后一次遍历列表中的一个数字,直到找到比最后一个数字大1位数的数字.此时已找到丢失的数字.

第二种算法:我保持列表不变.我创建另一个数组,所有数字1-N已经排序.我遍历这个新列表中的每个数字,并将其与原始列表中的数字进行比较.一旦我在原始列表中找到该号码,我就从列表中删除该号码(并在这样做时减小该列表的大小,假设这是一个动态数据结构).我为每个号码都这样做.如果一个数字遍历整个列表并且列表大小相同,那就是缺少的数字.

我认为算法2会更快,只是因为它减少了列表的大小,并且最多只能完成1次完整传递,最多它应该是O(1)(如果你点击了你的搜索权限就可以了).

第一个算法是O(nlogn),因为你正在进行排序,然后再次迭代列表.

或者也许他们都是O(nlogn)？自从昨晚以来,这一直困扰着我,因为这看起来很简单.

Answer 1

计算它们的总和,然后从它应该是的总和(n(n + 1)/ 2)中取出计算的总和

ShouldBeSum = N * (N+1) / 2;
MissingNumber = ShouldbeSum - CalculatedSum