Single Number

Posted on Edited on In Disqus:

Single Number I

问题：给定一个数组，除了其中一个数出现一次，其他数都出现了两次，找到这个数。

最简单的办法用莫过于用map统计每个数出现的次数，但这除了需要遍历数组外，还需要遍历map，且需要O(n)空间。

使用异或操作更为方便，根据a xor a = 0和a xor 0 = a，

1
2
3
4
5
6
7
8
9
int singleNumber(vector<int>& nums) {
  int ret = 0;

  for (auto n : nums) {
    ret ^= n;
  }

  return ret;
}

成对的数字进行xor后是0，最后ret便是只出现一次的那个数字。

Single Number II

方法1

问题：给定一个数组，除了其中一个数出现一次，其他数都出现了三次，找到这个数。

此时I的xor方法不可用，因为出现次数是奇数次。

考虑每个数的二进制表示，但凡这个数出现了三次，那么二进制表示中，如果某个bit有1，则这个1也在该bit上出现了三次。统计所有数字每个bit上1出现的次数，最后mod 3，余数就是那个数相应bit上的值。

1
2
3
4
5
6
7
2    2    2    11   11   11   12
0010 0010 0010 1011 1011 1011 1000
                              ----
count 1 for each bit,
bit index: 3 2 1 0
count:     4 0 6 3
mod 3:     1 0 0 0

以下是代码，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int singleNumber(vector<int>& nums) {
  vector<int> count(32, 0);

  for (auto n : nums) {
    for (int j = 0; j != count.size(); ++j) {
      if ((n >> j) & 1 != 0) {
        count[31 - j] += 1;
      }
    }
  }

  int result = 0;
  for (int i = 0; i != count.size(); ++i) {
    result |= (count[31 - i] % 3) << i;
  }

  return result;
}

以上代码是遍历每个数，统计每个数中bit为1的数目。还可以遍历每个bit，统计所有数字该bit上1的数目，这样可以合并两个for。

1
2
3
4
5
6
7
8
9
10
11
12
int singleNumber(vector<int>& nums) {
  vector<int> count(32, 0);
  int result = 0;

  for (int i = 0; i != count.size(); ++i) {
    for (auto n : nums) {
      count[31 - i] += (n >> i) & 1;
    }
    result |= (count[31 - i] % 3) << i;
  }
  return result;
}

方法2

但是上述方法需要O(n)的空间。在这个discuss中看到了更好的方法，结合例子能明白做了什么，但是无法理解这样位操作的idea是如何想出来的。。。最后在另一个blog和另一个disscus中找到了另一个方法，用了卡诺图。

在上面的代码中，每个bit的计数器count[31 - i]值为多少是无所谓的，最终需要的只是count[31 - i] % 3的结果。每当计数器为3，可以把它重置为0，即0 (00) -> 1 (01) -> 2 (10) -> 0 (00)，因此可以使用一个Two Bit Counter来表示状态的转换，

1
2
3
4
5
6
7
8
对于数字的每个bit b，
old_two, old_one b -> two, one
0        0       0    0    0
0        1       0    0    1
1        0       0    1    0
0        0       1    0    1
0        1       1    1    0
1        0       1    0    0

上图变为卡诺图，

1
2
3
4
5
two:                       one:
     old_two old_one       old_two old_one
     00 01 10              00 01 10
b 0   0  0  1         b 0   0  1  0
  1   0  1  0           1   1  0  0

可以得到，

1
2
two = (old_two & ~old_one & ~b) | (~old_two & old_one & b)
one = (~old_two & old_one & ~b) | (~old_two & ~old_one & b)

由上面的式子可得，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int singleNumber(vector<int>& nums) {
  vector<int> count(32, 0);
  int result = 0;

  for (int i = 0; i != count.size(); ++i) {
    int two = 0;
    int one = 0;

    int old_two, old_one;
    for (auto n : nums) {
      old_two = two;
      old_one = one;
      int b = (n >> i) & 1;

      two = (old_two & ~old_one & ~b) | (~old_two & old_one & b);
      one = (~old_two & old_one & ~b) | (~old_two & ~old_one & b);
    }

    result |= (one << i);
  }

  return result;
}

接着发现blog里面实际上是对每个数字使用了上面的公式，而不是对数字的每个bit。观察上面的状态转换图和代码，对每个bit进行计算的时候，two和one始终都是在使用最后一个bit，没有进位的情况，如果多个bit同时计算，没有相互影响，不会有问题，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int singleNumber(vector<int>& nums) {
  int two = 0;
  int one = 0;

  for (auto n : nums) {
    int old_two = two;
    int old_one = one;

    two = (old_two & ~old_one & ~n) | (~old_two & old_one & n);
    one = (~old_two & old_one & ~n) | (~old_two & ~old_one & n);
  }

  return one;
}

上面的公式还可简化，计算two时，由于old_two = two且old_one = one，

1
2
3
two = (two & ~one & ~b) | (~two & one & b)
    = one & (two ^ b)
one = (~old_two & one & ~b) | (~old_two & ~one & b)

对one还可以简化，在状态转换表中用11代替old_two和old_one的10，进而在式子中消除old_two（one = two | (one ^ b)）。还有，如果使用了不同的状态转换表示，最后的结果也会有所差异。

Single Number III

问题：给定一个数组，除了其中两个数分别出现一次，其他数都出现了两次，找到这两个数。

用I的方法来做的话，ret是那两个数的xor，因此现在需要从ret中区分出两个数。

假设有如下数组，且ret中只有第3个bit被置为1，

1
2
[a, b, c, b, d, a]
ret = c ^ d

如果ret中某一bit出现了1，那么这两个数中，对应的bit必然是一个为1，另一个为0。根据该bit是否为1，可以把原数组分为两组，c和d不会在同一个组里，有下面两种情况，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1. 某个组里只有c或d
[c]
[a, b, d, b, a]
c = c
a ^ b ^ d ^ b ^ a = d

[a b c b a]
[d]
a ^ b ^ c ^ b ^ a = a
d = d

2. 每个组除了c或d，还有其他数
[a c a]
[b d b]
a ^ c ^ a = c
b ^ d ^ b = d

无论是情况1或2，如果某个组除了c或d，还有其他数，那么这些数必定是成对出现的。接下来把两个组的数分别xor即可，两个xor的结果就是c和d。

上述例子是假设了ret中只有一个bit被置为1，如果ret中有多个bit为1，则只需要根据其中的一个bit来分组，因此需要从ret中提取出一个为1的bit。下面提取最后一个为1的bit，

1
2
3
4
5
6
7
last_bit_one = r & ~(r - 1);

若ret为1010010，
ret           1010010
r- 1          1010001
~(r - 1)      0101110
r & ~(r - 1)  0000010
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<int> singleNumber(vector<int>& nums) {
  int r = 0;

  for (auto n : nums) {
    r ^= n;
  }
  int last_bit_one = r & ~(r - 1);

  vector<int> res(2, 0);
  for (auto n : nums) {
    if ((last_bit_one & n) != 0) {
      res[0] ^= n;
    } else {
      res[1] ^= n;
    }
  }

  return res;
}

扩展

I

问题：给定一个数组，除了其中一个数出现两次，其他数都出现了三次，找到这个数。

类似Single Number II，如果用vector对值为1的bit进行计数，那么最后mod 3，如果余数为2，那么该bit就是那个数字的相应bit，代码改为result |= (count[31 - i] % 3 == 2) << i;。

如果是使用第二个方法，直接返回two即可。

II

问题：给定一个数组，除了其中一个数出现l次，其他数都出现了k次，找到这个数。

References

  1. My own explanation of bit manipulation method, might be easier to understand
  2. Constant space solution
  3. leetcode Single Number II - 位运算处理数组中的数
  4. Explain using xor to find two non-duplicate integers in an array
  5. Single Number II : How to come up with Bit Manipulation Formula