Fork me on GitHub

Find the duplicated number

Posted on

Linkage

https://leetcode.com/problems/find-the-duplicate-number/description/

This is a tricky question, we use binary search to solve it.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int findDuplicate(int[] nums) {
        return findDuplicateIndex(nums, 0, nums.length - 1);
    }
    
    public int findDuplicateIndex(int[] nums, int small, int big) {
        if (small == big) return small;
        
        int biggerThanMiddleCount = 0;
        int middle = (small + big) / 2;
        int count = big - small + 1;
        for (int num : nums) {
            if (num > middle && num <= big)
                biggerThanMiddleCount += 1;
        }
        if (biggerThanMiddleCount <= count / 2)
            return findDuplicateIndex(nums, small, middle);
        else
            return findDuplicateIndex(nums, middle+1, big);
    }
}