287. Find the Duplicate Number

Binary Search

class Solution {
    public int findDuplicate(int[] nums) {
        int left = 1, right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) >>> 1;

            int count = 0;
            for (int num : nums) {
                if (num <= mid) {
                    count++;
                }
            }

            if (count <= mid) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }
}

Bit

class Solution {
    public int findDuplicate(int[] nums) {
        int n = nums.length - 1;
        int bitCount = Integer.SIZE - Integer.numberOfLeadingZeros(n);

        int duplicate = 0;
        for (int i = 0; i < bitCount; i++) {
            int mask = 1 << i;
            int oneTimesInNums = 0, oneTimesInN = 0;
            for (int j = 0; j < nums.length; j++) {
                if ((nums[j] & mask) != 0) {
                    oneTimesInNums++;
                }
                if (j > 0 && (j & mask) != 0) {
                    oneTimesInN++;
                }
            }

            if (oneTimesInNums > oneTimesInN) {
                duplicate |= mask;
            }
        }

        return duplicate;
    }
}

Two Pointers

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;
            }
        }
    }
}

Reference

287. Find the Duplicate Number