Welcome to Subscribe On Youtube
Question
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
Algorithm
Binary search
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.
Bit
For each digit, the number of 1
s in this digit in all numbers from 0 to n-1 should be fixed
. If there are more 1
s 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.
Code
-
import java.util.Arrays; public class Find_the_Duplicate_Number { class Solution_bit { public int findDuplicate(int[] nums) { int res = 0, len = nums.length; for (int i = 0; i < 32; ++i) { int bit = (1 << i), cnt1 = 0, cnt2 = 0; for (int k = 0; k < len; ++k) { // len is actually n+1 if ((k & bit) > 0) ++cnt1; // 1s count with no duplicate if ((nums[k] & bit) > 0) ++cnt2; // 1s count with no duplicate } if (cnt2 > cnt1) res += bit; } return res; } } class Solution { public int findDuplicate(int[] nums) { int left = 1, right = nums.length; while (left < right) { int mid = left + (right - left) / 2, cnt = 0; for (int num : nums) { if (num <= mid) ++cnt; } // eg. 1,1,1,1,1,1,1,2 // eg. 1,2,2,2,2,2,2,2 if (cnt <= mid) left = mid + 1; else right = mid; } return right; } } class Solution_sort { public int findDuplicate(int[] nums) { Arrays.sort(nums); for (int i = 1; i < nums.length; i++) { if (nums[i] == nums[i-1]) { return nums[i]; } } return -1; } } }
-
// OJ: https://leetcode.com/problems/find-the-duplicate-number/ // Time: O(NlogN) // Space: O(1) class Solution { public: int findDuplicate(vector<int>& A) { int L = 1, R = A.size() - 1; while (L < R) { int M = (L + R) / 2, cnt = 0; for (int n : A) cnt += n <= M; if (cnt <= M) L = M + 1; else R = M; } return L; } };
-
class Solution: def findDuplicate(self, nums: List[int]) -> int: left, right = 1, len(nums) - 1 while left < right: mid = (left + right) >> 1 cnt = sum(v <= mid for v in nums) if cnt > mid: right = mid else: left = mid + 1 return left ############ class Solution(object): def findDuplicate(self, nums): """ :type nums: List[int] :rtype: int """ n = len(nums) - 1 start, end = 1, n while start + 1 < end: mid = start + (end - start) / 2 count = 0 for num in nums: if num < mid: count += 1 if count >= mid: end = mid else: start = mid if nums.count(start) > nums.count(end): return start return end