287. Find the Duplicate Number

Question

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.

Example 1:

Input: [1,3,4,2,2]
Output: 2

Example 2:

Input: [3,1,3,4,2]
Output: 3

Thinking:

• Method 1: 使用了额外内存，cheating

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

• Method 2：求链表的入环点
  • 将每一位的数值定义为下一个数字的位置。
  • 定义快指针慢指针。

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0, fast = 0;
        do{
            slow = nums[slow];
            fast = nums[nums[fast]];
        }while(slow != fast);
        fast = 0;
        while(fast != slow){
            fast = nums[fast];
            slow = nums[slow];
        }
        return fast;
    }
}

Second time

1. This question can be compared with the cyclic list question.
2. The difference between this two question is we use the index as the “pointer” in this question.

   class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0, fast = 0;
        do{
            slow = nums[slow];
            fast = nums[nums[fast]];
        }while(slow != fast);
        slow = 0;
        while(slow != fast){
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
   }