Single Number II

描述

Given an array of integers, every element appears three times except for one. Find that single one.

Note:Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

分析

本题和上一题 Single Number，考察的是位运算。

方法1：创建一个长度为sizeof(int)的数组count[sizeof(int)]，count[i]表示在在i位出现的1的次数。如果count[i]是3的整数倍，则忽略；否则就把该位取出来组成答案。

方法2：用one记录到当前处理的元素为止，二进制1出现“1次”（mod 3 之后的 1）的有哪些二进制位；用two记录到当前计算的变量为止，二进制1出现“2次”（mod 3 之后的 2）的有哪些二进制位。当one和two中的某一位同时为1时表示该二进制位上1出现了3次，此时需要清零。即用二进制模拟三进制运算。最终one记录的是最终结果。

代码1

  1. // Single Number II
  2. // 方法1，时间复杂度O(n)，空间复杂度O(1)
  3. class Solution {
  4. public:
  5.     int singleNumber(vector<int>& nums) {
  6.         const int W = sizeof(int) * 8; // 一个整数的bit数，即整数字长
  7.         int count[W];  // count[i]表示在在i位出现的1的次数
  8.         fill_n(&count[0], W, 0);
  9.         for (int i = 0; i < nums.size(); i++) {
  10.             for (int j = 0; j < W; j++) {
  11.                 count[j] += (nums[i] >> j) & 1;
  12.                 count[j] %= 3;
  13.             }
  14.         }
  15.         int result = 0;
  16.         for (int i = 0; i < W; i++) {
  17.             result += (count[i] << i);
  18.         }
  19.         return result;
  20.     }
  21. };

代码2

  1. // Single Number II
  2. // 方法2，时间复杂度O(n)，空间复杂度O(1)
  3. class Solution {
  4. public:
  5.     int singleNumber(vector<int>& nums) {
  6.         int one = 0, two = 0, three = 0;
  7.         for (int i : nums) {
  8.             two |= (one & i);
  9.             one ^= i;
  10.             three = ~(one & two);
  11.             one &= three;
  12.             two &= three;
  13.         }
  15.         return one;
  16.     }
  17. };

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/bitwise-operations/single-number-ii.html