Find the Duplicate Number

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的数组nums[]，里面的元素nums[i]都在1到n之间，只有一个重复元素，让我们找到这个元素，空间复杂度为O(1)，时间复杂度不多于O(n^2)。我们可以将数组排序，然后通过二分法找到重复的元素，排序之后，如果中间的元素的值小于或等于中间元素的下标，即nums[m] <= m, 说明重复的元素肯定在m的左边（因为元素的值是从1开始，如果左边没有重复元素，所以中间元素的值肯定会大于中间元素的下标。），让右指针变为m - 1; 否则让左指针变为m+1。这样时间复杂度为O(nlogn)。代码如下：

public class Solution {
    public int findDuplicate(int[] nums) {
        Arrays.sort(nums);
        int l = 0; 
        int r = nums.length - 1;
        while(l < r) {
            int m = l + (r - l) / 2;
            if(nums[m] <= m) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return nums[l];
    }
}

还有一个很巧妙的方法，只需要O(n)的时间复杂度。我们从第一个元素开始，如果nums[nums[i]]大于0，就把nums[nums[i]]设定为负数，因为只有一个元素重复，当我们往后处理，遇到nums[nums[i]]小于0，说明我们之前访问过这个元素，因此当前元素的值为重复的元素。代码如下：

public class Solution {
    public int findDuplicate(int[] nums) {
        int result = 0;
        for(int i = 0; i < nums.length; i++) {
            if(nums[Math.abs(nums[i])] > 0) {
                nums[Math.abs(nums[i])] = - nums[Math.abs(nums[i])];
            } else {
                result = Math.abs(nums[i]);
            }
        }
        return result;
    }
}