JunyiCode
4/14/2020 - 2:33 AM

287. Find the Duplicate Number

快慢指针 similar to 142

/*
draw
*/

class Solution {
    public int findDuplicate(int[] nums) {
        if(nums == null || nums.length <= 1)
            return -1;
        int slow = nums[0];
        int fast = nums[nums[0]];
        
        while(slow != fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        
        fast = 0;
        
        while(slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        
        return slow;
    }
}
class Solution {
    public int findDuplicate(int[] nums) {
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i-1]) {
                return nums[i];
            }
        }

        return -1;
    }
}