首页 > ACM题库 > LeetCode > LeetCode-Single Number II[位运算]
2014
03-28

LeetCode-Single Number II[位运算]

Single Number II

iven 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?

链接:http://oj.leetcode.com/problems/single-number-ii/

问题:给一个数组,里面只有一个数字一次,其它数字都出现3次,找出这个出现一次的数字,要求时间复杂度为O(n),空间复杂度为O(1)。

例子:

Input: arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3}
Output: 2

可以通过排序在O(nlogn)的时间内解决,也可以用hash,但是最坏的情况下复杂度可能会超过O(n),hash需要的空间复杂度也比较大。

前面的Single Number[位运算] 是一个很简单的位运算题目。

这里的思想是还是位运算的方法解决。并不是简单的异或等操作,因为所有的数字都是出现奇数次。大家可以先参考careercup上面的这个面试题

这里我们需要重新思考,计算机是怎么存储数字的。考虑全部用二进制表示,如果我们把 第 ith  个位置上所有数字的和对3取余,那么只会有两个结果 0 或 1 (根据题意,3个0或3个1相加余数都为0).  因此取余的结果就是那个 “Single Number”.

一个直接的实现就是用大小为 32的数组来记录所有 位上的和。

int singleNumber(int A[], int n) {
    int count[32] = {0};
    int result = 0;
    for (int i = 0; i < 32; i++) {
        for (int j = 0; j < n; j++) {
            if ((A[j] >> i) & 1) {
                count[i]++;
            }
        }
        result |= ((count[i] % 3) << i);
    }
    return result;
}

这个算法是有改进的空间的,可以使用掩码变量:

  1. ones   代表第ith 位只出现一次的掩码变量
  2. twos  代表第ith 位只出现两次次的掩码变量
  3. threes  代表第ith 位只出现三次的掩码变量

假设在数组的开头连续出现3次5,则变化如下:

ones = 101
twos = 0
threes = 0
--------------
ones = 0
twos = 101
threes = 0
--------------
ones = 0
twos = 0
threes = 101
--------------

当第 ith 位出现3次时,我们就 ones  和 twos  的第 ith 位设置为0. 最终的答案就是 ones。

int singleNumber(int A[], int n) {
    int ones = 0, twos = 0, threes = 0;
    for (int i = 0; i < n; i++) {
        twos |= ones & A[i];
        ones ^= A[i];// 异或3次 和 异或 1次的结果是一样的
       //对于ones 和 twos 把出现了3次的位置设置为0 (取反之后1的位置为0)
        threes = ones & twos;
        ones &= ~threes;
        twos &= ~threes;
    }
    return ones;
}

参考:http://oj.leetcode.com/discuss/857/constant-space-solution


  1. 后面的掩码变量部分乍一看比较难理解,其实就是把32位按照一个整体来看待。