0287. 寻找重复数 Find the Duplicate Number

统计字典

创建一个字典, 用于统计每个整数出现的次数
遍历数组, 并更新字典
遍历字典, 找出出现次数大于1的整数, 这个就是重复的数
如果没有重复的整数, 就返回 -1

#![allow(unused)]
fn main() {
use std::collections::HashMap;

// 使用哈稀表计数器
// 时间复杂度: O(n)
// 空间复杂度: O(n)
pub fn find_duplicate1(nums: Vec<i32>) -> i32 {
    let len: i32 = nums.len() as i32;
    assert!(len >= 2);
    let n: i32 = len - 1;
    assert!(n >= 1);
    for &num in &nums {
        assert!(num >= 1 && num <= n);
    }

    let mut map: HashMap<i32, usize> = HashMap::new();
    for &num in &nums {
        map.entry(num).and_modify(|count| *count += 1).or_insert(1);
    }
    for (key, count) in map {
        if count > 1 {
            return key;
        }
    }
    -1
}
}

这个方法的时间复杂度是 O(n), 空间复杂度是 O(n).

集合

这个方法是对上述方法的优化:

创建一个集合, 用于记录整数值是否出现过
遍历数组, 并将它存入到集合中, 如果此时集合中已经存在同样的整数, 这个整数就是重复的
否则返回 -1

#![allow(unused)]
fn main() {
use std::collections::HashSet;

// 使用 HashSet 来记录整数是否被插入过
// 时间复杂度: O(n)
// 空间复杂度: O(n)
pub fn find_duplicate11(nums: Vec<i32>) -> i32 {
    let mut set: HashSet<i32> = HashSet::with_capacity(nums.len());
    for &num in &nums {
        // 如果元素已经在集合中, 就返回false; 如果是第一次插入, 就返回 true.
        if !set.insert(num) {
            return num;
        }
    }
    -1
}
}

这个方法的时间复杂度是 O(n), 空间复杂度是 O(n).

BitSet

使用 bitset 来存储整数值是否出现过.

#![allow(unused)]
fn main() {
// BitSet
// 利用标志位来标记出现次数多于一次的整数.
// 时间复杂度: O(n)
// 空间复杂度: O(n)
pub fn find_duplicate2(nums: Vec<i32>) -> i32 {
    let mut bits: Vec<bool> = vec![false; nums.len()];
    for num in nums {
        let num_usize = num as usize;
        if bits[num_usize] {
            return num;
        }
        bits[num_usize] = true;
    }
    -1
}
}

这个方法的时间复杂度是 O(n), 空间复杂度是 O(n).

这个方法比较浪费空间, 因为每个索引位置占了一个字节. 我们可以改进一下它, 实现一个节省空间的 bitset, 每个索引位置只占一个比特:

#![allow(unused)]
fn main() {
// BitSet
// 利用标志位来标记出现次数多于一次的整数.
// 使用真正的bitset, 而不是 Vec<bool>.
// 时间复杂度: O(n)
// 空间复杂度: O(n)
pub fn find_duplicate22(nums: Vec<i32>) -> i32 {
    let mut bits = [0u64; (100_000) / 64 + 1];

    for num in nums {
        let num_usize = num as usize;
        let slot = num_usize / 64;
        let pos = num_usize % 64;

        let mask = 1 << pos;
        // 检查特定的比特位.
        if bits[slot] & mask == mask {
            return num;
        }
        bits[slot] |= mask;
    }
    -1
}
}

上述几个方法的思路都类似, 只是用于存放整数索引的方式不同.

暴力法 Brute force

先对数组进行排序 (这里已经不符合题目要求了)
然后遍历数组, 找到左右相邻元素之间有重复的

#![allow(unused)]
fn main() {
// 先对数组排序, 然后遍历它, 找到重复元素
// 时间复杂度: O(n log(n))
// 空间复杂度: O(n)
// 但是会修改原数组.
pub fn find_duplicate5(nums: Vec<i32>) -> i32 {
    let mut nums = nums;
    nums.sort();

    let len = nums.len();
    for i in 0..(len - 1) {
        if nums[i] == nums[i + 1] {
            return nums[i];
        }
    }
    -1
}
}

因为使用了排序算法, 这个方法比较慢, 时间复杂度是 O(n log(n)), 空间复杂度是 O(1)

使用负数来标记该整数已经出现过

这个方法也会修改数组的值, 其核心思想是利用整数的符号位来标记整数是否存在. 其步骤如下:

遍历数组, 计数当前元素 m 的绝对值
以该绝对值作为元素的索引, 找到数组中对应的元素 k
如果元素 k 本身是一个正数, 就把它转成对应的负数
如果元素 k 是一个负数, 说明之前就有相同的整数值 m 存在过, 就返回它

下面以 [1, 2, 3, 3, 4] 数组为例展示整个过程:

negative as index

当遍历到 i = 3 时, nums[3] == -3, 说明数组的左侧部分就有整数 3 存在过, 这个整数就是重复的.

相应的代码实现如下:

#![allow(unused)]
fn main() {
// 使用正负数来标记该整数已经出现过
// 时间复杂度: O(n)
// 空间复杂度: O(1)
// 但是它需要修改数组
pub fn find_duplicate4(nums: Vec<i32>) -> i32 {
    let mut nums = nums;
    let len = nums.len();
    for i in 0..len {
        let index: i32 = nums[i].abs();
        let index_usize: usize = index as usize;
        if nums[index_usize] < 0 {
            return index;
        }
        nums[index_usize] *= -1;
    }
    -1
}
}

时间复杂度是 O(n), 空间复杂度是 O(1)

数据结构与算法 - Rust 语言实现

0287. 寻找重复数 Find the Duplicate Number

统计字典

集合

BitSet

暴力法 Brute force

使用负数来标记该整数已经出现过