287. Find the Duplicate Number
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.
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 = [1,1] Output: 1
Example 4:
Input: nums = [1,1,2] Output: 1
Constraints:
2 <= n <= 3 * 104nums.length == n + 11 <= nums[i] <= n- All the integers in
numsappear 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 without modifying the array
nums? - Can you solve the problem using only constant,
O(1)extra space? - Can you solve the problem with runtime complexity less than
O(n2)?
Rust Solution
struct Solution;
impl Solution {
fn find_duplicate(nums: Vec<i32>) -> i32 {
let n = (nums.len() - 1) as i32;
let mut low = 1;
let mut high = n;
while low < high {
let mid = low + (high - low) / 2;
let mut count = 0;
for &x in &nums {
if x <= mid {
count += 1;
}
}
if count <= mid {
low = mid + 1;
} else {
high = mid;
}
}
low
}
}
#[test]
fn test() {
let nums = vec![1, 3, 4, 2, 2];
let res = 2;
assert_eq!(Solution::find_duplicate(nums), res);
let nums = vec![3, 1, 3, 4, 2];
let res = 3;
assert_eq!(Solution::find_duplicate(nums), res);
}
Having problems with this solution? Click here to submit an issue on github.