Description
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 using 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
Example 3:
Input: nums = [3,3,3,3,3]
Output: 3
Constraints:
1 <= n <= 105nums.length == n + 11 <= 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?
Solutions
Solution 1: Binary Search
We can observe that if the number of elements in [1,..x] is greater than x, then the duplicate number must be in [1,..x], otherwise the duplicate number must be in [x+1,..n].
Therefore, we can use binary search to find x, and check whether the number of elements in [1,..x] is greater than x at each iteration. This way, we can determine which interval the duplicate number is in, and narrow down the search range until we find the duplicate number.
The time complexity is O(n × log n), where n is the length of the array nums. The space complexity is O(1).
PythonJavaC++GoTypeScriptRustJavaScript
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
def f(x: int) -> bool:
return sum(v <= x for v in nums) > x
return bisect_left(range(len(nums)), True, key=f)(code-box)
class Solution {
public int findDuplicate(int[] nums) {
int l = 0, r = nums.length - 1;
while (l < r) {
int mid = (l + r) >> 1;
int cnt = 0;
for (int v : nums) {
if (v <= mid) {
++cnt;
}
}
if (cnt > mid) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
}(code-box)
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = (l + r) >> 1;
int cnt = 0;
for (int& v : nums) {
cnt += v <= mid;
}
if (cnt > mid) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
};(code-box)
func findDuplicate(nums []int) int {
return sort.Search(len(nums), func(x int) bool {
cnt := 0
for _, v := range nums {
if v <= x {
cnt++
}
}
return cnt > x
})
}(code-box)
function findDuplicate(nums: number[]): number {
let l = 0;
let r = nums.length - 1;
while (l < r) {
const mid = (l + r) >> 1;
let cnt = 0;
for (const v of nums) {
if (v <= mid) {
++cnt;
}
}
if (cnt > mid) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}(code-box)
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
}
}(code-box)
/**
* @param {number[]} nums
* @return {number}
*/
var findDuplicate = function (nums) {
let l = 0;
let r = nums.length - 1;
while (l < r) {
const mid = (l + r) >> 1;
let cnt = 0;
for (const v of nums) {
if (v <= mid) {
++cnt;
}
}
if (cnt > mid) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};(code-box)
