0137. Single Number II

问题描述

第一种思路, 使用字典来计数

很直接的想法, 用字典来统计所有数值出现的次数, 然后遍历该字典, 找到次数为1的那个数值.

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

// map, brute force
// 使用字典来统计数值出现的次数
pub fn single_number1(nums: Vec<i32>) -> i32 {
    let mut map: HashMap<i32, usize> = HashMap::new();
    for &num in &nums {
        map.entry(num).and_modify(|count| *count += 1).or_insert(1);
    }
    for (num, count) in map {
        if count == 1 {
            return num;
        }
    }
    -1
}
}

第二种思路, 使用 BitVector

这个题目, 因为是奇数次重复的数, 所以不能再使用 0136. Single Number 里面的方法.

这个需要一个新的思路, 那就是 BitVector.

  • 遍历数组中的每个整数的每一个比特位
  • 对所有整数的同一个比特位求和, 然后对3取余, 因为大部分整数都出现了3次; 求得的余数, 就是落单的数值在该比特位的比特值
  • 当遍历完整数的所有比特位后, 就可以计算出落单整数的所有比特位的信息, 也就可以组装出了它的具体数值

基本的操作过程如下图所示:

bit vector

要注意的是, 这个解决方法, 可以解决数组中有奇数个重复的整数, 也可以解决有偶数个重复的整数. 也就是说, 它可以用来解 0136. Single Number.

具体的代码如下:

#![allow(unused)]
fn main() {
// bit vector
pub fn single_number2(nums: Vec<i32>) -> i32 {
    const DIGIT_LEN: usize = 32;

    let mut ans = 0;
    // 遍历所有比特位
    for i in 0..DIGIT_LEN {
        // 计数所有整数在该比特位处的和
        let sum = nums.iter().map(|num| num >> i & 1).sum::<i32>();
        // bit 的值就是落单的数在该比特位处的比特值.
        let bit = sum % 3;
        ans |= bit << i;
    }
    ans
}
}

第三种思路

TODO(Shaohua): Use ones and twos to record.