interviewalgo
, , ,
Source
Edit
History

260. 只出现一次的数字 III

Introduction

Question：260. 只出现一次的数字 III

Analysis

如果是只有一个出现一次的元素，那么我们可以对 nums 的所有值进行异或，那么得到的就是答案。而现在有两个元素，那么我们就会得到这两个元素的异或。

如果答案为 {a, b} 的话，那么对 nums 的所有值进行异或得到 a ^ b

假设我们已经知道了 a 和 b 在二进制第 k 位中不相同，那么我们就可以利用这个特性将整个数组

分成两部分：

  • 第 k 位为 0
  • 第 k 位为 1

这样这两部分都满足了“只有一个元素出现一次，其他元素均出现两次”，这样就将问题转化为一个简单的问题了。

我们知道两个值异或操作的特点就是，如果第 k 位值相同，那么结果的第 k 位为 0，第 k 位值不相同，那么结果的第 k 位就为 1。

因此，从 a ^ b 中找到一个值为 1 的位，即可解决掉这道题了。

虽然直接遍历 32 位找到这个位置的时间复杂度也是 O(1)。

但是我们可以通过位运算的方式来求解：

  • t & (t - 1) 可以将 t 最低位清零
  • (t & (t-1)) ^ t 则得到一个第 k 位为 1 的 mask，k 为 t 中第一个1的位置

emmm,由于 t & (t - 1) 会报 UB 的错误，需要把 int 改成 unsigned。

使用t & (t - 1)可以代替(t & (t-1)) ^ t。

Implement

1
2
3
4
5
6
7
8
9
10
11
vector<int> singleNumber(vector<int>& nums) {
    unsigned t = 0;
    for(auto i: nums) t ^= i;
    // unsigned mask = t & (-t);
    unsigned mask = (t & (t-1)) ^ t;
    unsigned a = 0;
    for(auto i: nums) if (i & mask) a ^= i;
    int res1 = static_cast<int>(a);
    int res2 =static_cast<int>(a ^ t); 
    return {res1,res2};
}

One More Thing