Description：
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
Note:
- You must not modify the array (assume the array is read only).
- You must use only constant, O(1) extra space.
- Your runtime complexity should be less than
O(n2). - There is only one duplicate number in the array, but it could be repeated more than once.
寻找n+1个数的数组中的唯一重复数字。数组里面的数字是1~N的。要求：时间复杂度O(n2)以下，空间复杂度O(1)。数组为只读。
思路：暴力和排序都是不符合要求的。暴力的优化就是二分。如果小于中间指针的数的个数大于中间指针的话，重复数一定会在前半段。否则在后半段。
时间复杂度为O(nlogn)空间复杂度为O(1).
public class Solution {
public int findDuplicate(int[] nums) {
int left = 0, right = nums.length - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
int cnt = 0;
for(int i=0; i<nums.length; i++) {
if(nums[i] <= mid)
cnt ++;
}
if(cnt > mid)
right = mid - 1;
else
left = mid + 1;
}
return left;
}
}
还有一种比较高效的解法就是映射找环路法。
借鉴网上的解法：
假设数组中没有重复，那我们可以做到这么一点，就是将数组的下标和1到n每一个数一对一的映射起来。比如数组是213,则映射关系为0->2, 1->1, 2->3。假设这个一对一映射关系是一个函数f(n)，其中n是下标，f(n)是映射到的数。如果我们从下标为0出发，根据这个函数计算出一个值，以这个值为新的下标，再用这个函数计算，以此类推，直到下标超界。实际上可以产生一个类似链表一样的序列。比如在这个例子中有两个下标的序列，0->2->3。
但如果有重复的话，这中间就会产生多对一的映射，比如数组2131,则映射关系为0->2, {1，3}->1, 2->3。这样，我们推演的序列就一定会有环路了，这里下标的序列是0->2->3->1->1->1->1->...，而环的起点就是重复的数。
public class Solution {
public int findDuplicate(int[] nums) {
int slow = 0;
int fast = 0;
// 找到快慢指针相遇的地方
do{
slow = nums[slow];
fast = nums[nums[fast]];
} while(slow != fast);
int find = 0;
// 用一个新指针从头开始，直到和慢指针相遇
while(find != slow){
slow = nums[slow];
find = nums[find];
}
return find;
}
}