287. Find the Duplicate Number

287. 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.

Example 1:

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

Example 2:

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

Note:

1. You must not modify the array (assume the array is read only). --说明不能sort array或者改变array里的元素

2. You must use only constant, O(1) extra space. --说明不能另存一个arr

3. Your runtime complexity should be less than O(n2).

4. There is only one duplicate number in the array, but it could be repeated more than once.

My Solutions:

不符合条件的方法有：

1. sort 然后iterate。Time: O(NlogN); Space: O(NlogN)

2. 用hashset储存见过的值。Time: O(N); Space: O(N)

3. 改变正负号。Time: O(N); Sapce: O(1)

For example, if the input array is [1,3,3,2]：

• for 1, flip the number at index 1, making the array [1,−3,3,2]

• for −3, flip the number at index 3, making the array [1,−3,3,−2]

• for 3, we'll notice that nums[3] is already negative, indicating that 3 has been seen before and hence is the duplicate number.

// #1
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;
}

// #2
public int findDuplicate(int[] nums) {
    Set<Integer> seen = new HashSet<Integer>();
    for (int num : nums) {
        if (seen.contains(num))
            return num;
        seen.add(num);
    }
    return -1;
}

// #3
 public int findDuplicate(int[] nums) {
    int numAtIndex = 0, result = 0;
    for(int i = 0; i < nums.length; i++){
         numAtIndex = Math.abs(nums[i]);
         if(nums[numAtIndex] <0){
             result = Math.abs(nums[i]);
             break;
         } else {
            nums[numAtIndex] = -nums[numAtIndex];     
         }
    }       
    return result;               
}

1. swap 数字，把数字放到正确的index上去。Time: O(N); Space: O(1)

an example $[3,3,5,4,1,3]$:

• $[\underline3,3,5,\underline4,1,3]$ // Compare nums[0] to nums[nums[0]] (i.e. nums[0] to nums[3]). 3!=4. Swap them. Now the first 3 will be swapped into its correct position, and position 0 has 4.

• $[\underline4,3,5,3,\underline1,3]$ // Compare nums[0] to nums[4]. 4 != 1. Not equal so swap again. Now 4 is in its correct position.

• $[\underline1,\underline3,5,3,4,3]$ // Compare nums[0] with nums[1]. Not equal, swap.

• $[\underline3,1,5,\underline3,4,3]$ // Now nums[0] == nums[3] (both are 3). 3 is in both positions 0 and position 3, so it's the duplicate.

public int findDuplicate(int[] nums) {
    while (nums[0] != nums[nums[0]]) {
        int nxt = nums[nums[0]];
        nums[nums[0]] = nums[0];
        nums[0] = nxt;
    }
    return nums[0];
}

符合条件的做法：

方法1：binary search ( The binary search is utilizing the fact that the duplicate number could only occur in the "denser" half of the array (This is only true, we have no missing numbers from 1 to n). So we should set low or high to move towards the denser half. Eventually when low exceeds high we will get the duplicated number.)

eg. [3,1,3,4,2], mid = 0+(4-0)/2=2, 找到小于等于mid的数量是2。因为count小于mid，说明duplicate数在mid之后，把l移位，l=2+(4-2)/2=3。

mid=3+(4-3)/2=3,找到小于等于mid的数量是4。因为count大于mid，说明duplicate数在mid之前，把r移位，r=3-1=2。

Time: O(NlogN); Space: O(1)

public int findDuplicate(int[] nums) {
    int l = 1, r = nums.length - 1;
    while (l + 1 < r) {
        int mid = l + (r - l) / 2;
        int count = 0;
        // count how many numbers in num are less than or equal to 'mid'
        for (int n : nums) {
            if (n <= mid) count++;
        }
        // too many numbers on the left
        if (count > mid)  r = mid;
        else l = mid;
    }
    // find the frequency of two numbers 
    int countL = 0, countR = 0;
    for (int n : nums) {
        if (n == l) countL++;
        if (n == r) countR++;
    }
    return countL > countR ? l : r;
}

方法2： The main idea is the same as the problem Linked List Cycle II. Use two-pointers the fast and the slow. The fast one goes forward two steps each time, while the slow one goes only one step each time. They must meet the same item when slow==fast. In fact, they meet in a circle, the duplicate number must be the entry point of the circle when visiting the array from nums[0]. Next, we just need to find the entry point. We use a point(we can use the fast one before) to visit form beginning with one step each time and do the same job to slow. When fast==slow, they meet at the entry point of the circle.

Time: O(N); Sapce: O(1)

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0, 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;
    }
}