什么算法可以在o（n）时间内从数组中找到丢失的整数？
假设我们有一个数组a，其元素的值范围为{1,2,3…2n}。一半的元素丢失，所以a=n的长度。
例如：
A=[1,2,5,3,10]，N=5
输出=4
最佳答案
假设数组上唯一有效的操作是读取元素和交换元素对，则可以在o（1）个额外的空间中执行此操作。
首先注意，问题的说明排除了数组包含重复项的可能性：它包含从1到2n的数字的一半。
我们执行一个快速选择类型算法。从m=1，m=2N+1开始，将数组旋转到（m+m）/2上如果数组左侧部分（元素所考虑的数组的切片的大小可以在o（n）时间和o（1）空间中进行，并且每次旋转大小为n的数组的一半。总体而言，时间复杂度为2n+n+n/ 2＋…+1
关于algorithm - 在O(n)中运行的最小丢失整数算法？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/42403408/