从未排序的连续整数列表中查找缺失和重复的整数

Question

这个问题非常类似于如何在一个混洗连续整数数组中找到重复元素？,但有一些额外的要求.

您有一个连续整数列表,没有特定的顺序.无法保证这些整数的范围或列表中的元素数量.

此列表缺少一个整数,并包含另一个整数的副本.

这样一个列表的一个例子是{16,12,13,17,14,13}; 在这种情况下,缺少的整数是15,重复的是13.

考虑到小数据集和大数据集,找到这两个数字的最省时的方法是什么？有没有比O(n log n)更好的时间复杂度的解决方案,它不会阻塞小数据集？

Answer 1

实际上,您可以从引用的主题中应用该想法.但是,由于你有两个变化,你应该测量两件事.

例如,测量值的总和和平方和,并将它们与预期值进行比较.如果数字A重复且数字B丢失,您将拥有:

• sum - expected_sum = AB
• sum_of_squares - expected_sum_of_squares = A ^ 2-B ^ 2

具有(AB)和(A ^ 2-B ^ 2),您可以得到(A + B)=(A ^ 2-B ^ 2)/(AB).

有(A + B)和(AB)你可以得到A =(A + B)/ 2 +(AB)/ 2和B =(A + B)/ 2-(AB)/ 2