Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/287.html
Given an array of integers nums
containing n + 1
integers where each integer is in the range [1, n]
inclusive.
There is only one repeated number in nums
, return this repeated number.
You must solve the problem without modifying the array nums
and uses only constant extra space.
Example 1:
Input: nums = [1,3,4,2,2] Output: 2
Example 2:
Input: nums = [3,1,3,4,2] Output: 3
Constraints:
1 <= n <= 105
nums.length == n + 1
1 <= nums[i] <= n
- All the integers in
nums
appear only once except for precisely one integer which appears two or more times.
Follow up:
- How can we prove that at least one duplicate number must exist in
nums
? - Can you solve the problem in linear runtime complexity?
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; } } } ############ class Solution { public int findDuplicate(int[] nums) { int left = 1, right = nums.length - 1; while (left < right) { int mid = (left + right) >> 1; int cnt = 0; for (int v : nums) { if (v <= mid) { ++cnt; } } if (cnt > mid) { right = mid; } else { left = mid + 1; } } return left; } }
-
// 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
-
func findDuplicate(nums []int) int { left, right := 1, len(nums)-1 for left < right { mid := (left + right) >> 1 cnt := 0 for _, v := range nums { if v <= mid { cnt++ } } if cnt > mid { right = mid } else { left = mid + 1 } } return left }
-
function findDuplicate(nums: number[]): number { let left = 1, right = nums.length - 1; while (left < right) { const mid = (left + right) >> 1; let cnt = 0; for (let v of nums) { if (v <= mid) { ++cnt; } } if (cnt > mid) { right = mid; } else { left = mid + 1; } } return left; }
-
/** * @param {number[]} nums * @return {number} */ var findDuplicate = function (nums) { let left = 1, right = nums.length - 1; while (left < right) { const mid = (left + right) >> 1; let cnt = 0; for (let v of nums) { if (v <= mid) { ++cnt; } } if (cnt > mid) { right = mid; } else { left = mid + 1; } } return left; };
-
impl Solution { #[allow(dead_code)] pub fn find_duplicate(nums: Vec<i32>) -> i32 { let mut left = 0; let mut right = nums.len() - 1; while left < right { let mid = (left + right) >> 1; let cnt = nums .iter() .filter(|x| **x <= mid as i32) .count(); if cnt > mid { right = mid; } else { left = mid + 1; } } left as i32 } }