[LeetCode]Find the Duplicate Number

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

	class Solution {
	public:
	int findDuplicate(vector<int>& nums) {
	int len = nums.size(), lo = 1, hi = len - 1;
	while(lo < hi)
	{
	int mid = lo + (hi - lo) / 2, count = 0;
	for(auto& num : nums)
	if(num <= mid)++count;
	if(count <= mid)
	lo = mid + 1;
	else
	hi = mid;
	}
	return lo;
	}
	};

view raw Find the Duplicate Numbe_1.cpp hosted with ❤ by GitHub

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

	class Solution {
	public:
	int findDuplicate(vector<int>& nums) {
	if(nums.size() < 2)return 0;
	int len = nums.size(), slow = nums[0], fast = nums[nums[0]];
	while(slow != fast)
	{
	slow = nums[slow];
	fast = nums[nums[fast]];
	}
	slow = 0;
	while(slow != fast)
	{
	slow = nums[slow];
	fast = nums[fast];
	}
	return slow;
	}
	};

view raw Find the Duplicate Numbe_2.cpp hosted with ❤ by GitHub

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

	class Solution {
	public:
	int findDuplicate(vector<int>& nums) {
	if(nums.size() < 2)return 0;
	int n = nums.size() - 1;
	vector<int> a(32, 0), b(32, 0);
	for(int i = 0; i < 32; ++i)
	{
	for(int j = 0; j <= n; ++j)
	{
	if((nums[j] >> i) & 1)
	++a[i];
	if((j >> i) & 1)
	++b[i];
	}
	}
	int dup = 0;
	for(int i = 0; i < 32; ++i)
	if(a[i] > b[i])
	dup |= (1 << i);
	return dup;
	}
	};

view raw Find the Duplicate Numbe_3.cpp hosted with ❤ by GitHub