QeuroIzoのBlog

hello world

0%

15. 只出现一次的数字 II

发表于

题目：

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例：

1
2
输入: [2,2,3,2]
输出: 3

方法一：

代码：

1
2
3
4
5
6
7
8
9
10
11
12
int singleNum(vector<int>& nums)
{
    int res = 0;
    for(int i = 0; i < 32; i++) {
        int count = 0;
        for(int j = 0; j < nums.size(); j++) {
            count += (nums[j] >> i) & 1;
        }
        res += (count % 3) << i;
    }
    return res;
}

解析：

  1. 首先：为什么i < 32?
    int型占4个字节，即32位，所以int的大小为 int$\in$ [$-2^{31}$, $2 ^ {31} -1$]
  2. 时间复杂度为：O(32n) <===> O(n)；
  3. 虽然是二进制，但是运算法则和十进制并无差异，变的只是进制而已；
  4. 因为要确定一个数字，所以$\%3$会让那个数字显示出来在二进制形式下，那个位置有1。

方法二：

代码：

1
2
3
4
5
6
7
8
int singleNum(vector<int>& nums) {
    int ones = 0, twos = 0;
     for(auto x : nums) {
         ones = (ones ^ x) & ~twos;
         twos = (twos ^ x) & ~ones;
     }
     return ones;

解析：

  1. 从 自动机 的角度出发；

  2. 状态机：（举例：）

    状态量 ones twos
    初始状态 0 0
    一个1 1 0
    两个1 0 1
    三个1 0 0

  3. 三个状态一循环，比如有6个1， 则进行两轮循环，状态量为0   0