287 Find the Duplicate Number

287. Find the Duplicate Number​
1. Question
Given an arraynumscontainingn+ 1 integers where each integer is between 1 andn(inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
Note:
1.You must not modify the array (assume the array is read only).
2.You must use only constant, O(1) extra space.
3.Your runtime complexity should be less thanO(n^2).
4.There is only one duplicate number in the array, but it could be repeated more than once.
2. Implementation
(1) Binary Search
1
class Solution {
2
    public int findDuplicate(int[] nums) {
3
        int start = 0, end = nums.length - 1, mid = 0;
4
​
5
        while (start + 1 < end) {
6
            mid = start + (end - start) / 2;
7
​
8
            int count = countNum(nums, mid);
9
​
10
            if (count <= mid) {
11
                start = mid + 1;
12
            }
13
            else {
14
                end = mid;
15
            }
16
        }
17
​
18
        return countNum(nums, start) > start ? start : end;
19
    }
20
​
21
    public int countNum(int[] nums, int target) {
22
        int count = 0;
23
​
24
        for (int num : nums) {
25
            if (num <= target) {
26
                ++count;
27
            }
28
        }
29
        return count;
30
    }
31
}
Copied!
(2) Two Pointers
1
public class Solution {
2
    public int findDuplicate(int[] nums) {
3
        // Similar to Linked List Cycle II 
4
        // Use Two Pointers to find the begnning of loop
5
        // This is where the duplicate occur
6
        int fast = 0, slow = 0;
7
​
8
        do {
9
            fast = nums[nums[fast]];
10
            slow = nums[slow];
11
        } while (fast != slow);
12
​
13
        slow = 0;
14
​
15
        while (fast != slow) {
16
            fast = nums[fast];
17
            slow = nums[slow];
18
        }
19
        return slow;
20
    }
21
}
Copied!
3. Time & Space Complexity
Binary Search: 时间复杂度O(nlogn), 空间复杂度O(1)
Two Pointers: 时间复杂度O(n), 空间复杂度O(1)

278 First Bad Version

302 Smallest Rectangle Enclosing Black Pixels

Last modified 2yr ago

Copy link

Contents

287. Find the Duplicate Number

1. Question

2. Implementation

3. Time & Space Complexity

287. Find the Duplicate Number​

1. Question

2. Implementation

3. Time & Space Complexity

287. Find the Duplicate Number