287.Find the Duplicate Number

Posted on | In

Solution 1: accepted 6ms

The input contain integers between [1,n]. If the maximum value is n, then the array has to have n + 1 elements to make sure that there are repeated values.

For this question, we don’t divide the elements inside the array as we do for regular binary search questions. Instead, we divide the range and compare the mid point with every element in the array. For example, for range [1,10], mid is 5, if there are more than five elements are smaller than 5, we know the repeated value is smaller than 5 (Pigeonhole principle), so we get a new range [1,5].

Time: O(nlogn)
Space: O(1) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int findDuplicate(int[] nums) {
        if (nums == null || nums.length < 2) {
            return -1;
        }
        
        int lo = 1;
        int hi = nums.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            int count = 0;
            for (int n: nums) {
                if (n <= mid) {
                    count++;
                }
            }
            if (count <= mid) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        
        return lo;
    }
}

The old way (lo + 1 < hi) will have extra long code, not very elegant

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public int findDuplicate(int[] nums) {
        if (nums == null || nums.length < 2) {
            return -1;
        }
        
        int lo = 1;
        int hi = nums.length - 1;
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            int count = 0;
            for (int n: nums) {
                if (n <= mid) {
                    count++;
                }
            }
            if (count <= mid) {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        
        int count = 0;
        for (int n: nums) {
            if (n == lo) {
                count++;
            }
            if (count > 1) {
                return lo;
            }
        }
        
        return hi;
    }
}