287. Find the Duplicate Number

, , 
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) {
        int left = 1, right = nums.length - 1; // [left, right], 此为值的范围

        while (left < right) {
            int mid = (left + right) >>> 1;

            int count = 0;
            for (int num : nums) {
                if (num <= mid) {
                    count++; // 统计小于等于 mid 的数字有多少个
                }
            }

            if (count <= mid) {
                // 小于等于 mid 个，说明 [left, mid] 中不存在重复数字
                left = mid + 1;
            } else {
                // 大于 mid 个，说明 [left, mid] 存在重复数字
                right = mid;
            }
        }

        return left;
    }
}

Bit

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) {
        int duplicate = 0;

        int n = nums.length - 1;
        int bits = Integer.SIZE - Integer.numberOfLeadingZeros(n);

        for (int i = 0; i < bits; i++) {
            int mask = 1 << i;
            int bitCountInNums = 0, bitCountInN = 0;
            for (int j = 0; j < nums.length; j++) {
                if ((nums[j] & mask) != 0) {
                    bitCountInNums++;
                }
                if (j > 0 && (j & mask) != 0) {
                    bitCountInN++;
                }
            }
            if (bitCountInNums > bitCountInN) {
                duplicate |= mask;
            }
        }

        return duplicate;
    }
}

Two Pointers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0, fast = 0; // 快慢指针均从头节点开始，即索引为 0 的节点，不用纠结数组中的索引，理解为链表中的首个节点即可

        while (true) {
            fast = nums[nums[fast]];
            slow = nums[slow];

            if (fast == slow) {
                // 此时快慢指针相遇，需要进一步寻找环的入口，因为环的入口节点被多个节点指向，所以为重复数，注意重复数为指向的索引
                int curr = 0;
                while (curr != slow) {
                    curr = nums[curr];
                    slow = nums[slow];
                }
                return curr;
            }
        }
    }
}

根据题意，包含 n + 1 个整数的数组 nums，其数字都在 [1, n] 范围内，如 nums = [1, 3, 4, 2, 2]，此时共 5 个整数，n = 4，数字都在 [1, 4] 内，那么可将值作为索引，使用环形链表找环入口的解法解题即可。

References

287. Find the Duplicate Number