坚持每天一道题,刷题学习Rust.
示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2]
输出: 3
说明:
不能更改原数组(假设数组是只读的)。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字,但它可能不止重复出现一次。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-the-duplicate-number
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
注意要求:
struct Solution {}
impl Solution {
pub fn find_duplicate(nums: Vec<i32>) -> i32 {
//区间都是闭区间,左右都包含
let mut l = (1, (nums.len() / 2) as i32);
let mut r = ((nums.len() / 2 + 1) as i32, (nums.len() - 1) as i32);
loop {
let result = Self::find_internal(nums.as_slice(), l, r);
println!("l={:?},r={:?},result={:?}", l, r, result);
//在左边,加1是因为闭区间
if result.0 > l.1 - l.0 + 1 {
let len = l.1 - l.0;
if len == 0 {
//长度只有1表示找到了
return l.0;
}
r = (len / 2 + l.0 + 1, l.1);
l = (l.0, len / 2 + l.0);
} else {
//在右边
let len = r.1 - r.0;
if len == 0 {
return r.0; //长度只有1表示找到了
}
l = (r.0, len / 2 + r.0);
r = (len / 2 + r.0 + 1, r.1);
}
}
// panic!("not found");
}
fn find_internal(nums: &[i32], l: (i32, i32), r: (i32, i32)) -> (i32, i32) {
let mut countl = 0;
let mut countr = 0;
nums.iter().for_each(|i| {
if *i >= l.0 && *i <= l.1 {
countl += 1;
}
if *i >= r.0 && *i <= r.1 {
countr += 1;
}
});
(countl, countr)
}
}
另外还有一种弗洛伊德的乌龟和兔子(循环检测
看了半天还是没明白,还是二分搜索更清晰,不过代码略长.
欢迎关注我的github,本项目文章所有代码都可以找到.