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 * 104`
• `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.

• 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)`?

287. Find the Duplicate Number
``````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);
}
``````