Formatted question description: https://leetcode.ca/all/287.html
287 Find the Duplicate Number Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one. Example 1: Input: [1,3,4,2,2] Output: 2 Example 2: Input: [3,1,3,4,2] Output: 3 Note: You must not modify the array (assume the array is read only). => 不能给原数组排序 You must use only constant, O(1) extra space. => 不能哈希表 Your runtime complexity should be less than O(n^2). => 不能用 brute force There is only one duplicate number in the array, but it could be repeated more than once. @tag-array @tag-binarysearch
Using the binary search method, search in the interval [1, n], first find the midpoint mid, then traverse the entire array, count all the numbers less than or equal to mid,
- If the number is less than or equal to mid, the repeated value is between [mid+1, n],
- On the contrary, the repeated value should be between [1, mid-1], Until the search is completed, low index then is the repeated value we require.
For each digit, the number of 1s in this digit in all numbers from 0 to n-1 should be fixed. If there are more 1s in this digit in all numbers in the nums array, it means that the this
1 is in duplicated number. We can reproduce the repeated number by adding up all the 1 bits of the repeated number.