[LeetCode]Find the Duplicate Number

要求常数空间且不modify原数组。这样我们在First Missing Positive的方法就不能用了，如果没有不能modify原数组的条件这个方法依然是可以用的。
我们很明显的知道答案是有一个区间的的，即[1, n]。那么考虑在值域上进行二分如果小于等于mid的数的数量不变或者变少了，很明显答案在[mid + 1, hi]的区间内，反之，答案在[lo, mid]内。根据这个算法的代码如下，时间复杂度O(n * log n)，常数空间：


除此之外还有O(n)的做法，假设数组里没有重复，我们把数组每一个元素看成图中的一个节点，nums[i]代表有边从index i指向index为nums[i]的地方，那么这应该是是一个没有环的路径（类似linked list），但是如果有重复的话，路径里会出现环。那么题目就变成了在linked list里找环，这道题我们之前就做过了，直接套用算法即可，时间复杂度O(n)，代码如下：


最后我们还有一种位操作的算法，我们统计1-n每个位累计1的数量在和数组统计之后每个位累计1的数量进行比较，如果数组比其多说明此位置是1，否则是0。时间复杂度O(n)，但是空间复杂度是O(log n)。原因是我们之所以说32位，是因为我们限制了input的大小，但是如果我们不限制的话，假设n很大，那么我们需要用log n位去表示它的二进制。所以这不是常数空间，代码如下：