首页 > 代码库 > Leetcode :: Single Number II

Leetcode :: 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 I 是把所有都异或,最后就是答案,很明了;可是这里有3个,应该怎么办呢?

出现了三次的时候,如果仍然从位运算入手,特征是什么?设那个唯一的数是x,特征是,按int型32位计,其中某一位假设x在该位上是0,则情况应该是该位的1出现的次数是3的倍数,而如果是1,则应该是出现3n + 1次的1,根据这个特征,来计算那个唯一的数据;

设三个int, one、two、three,这里出现一次为  0 1   两次未 1 0 三次为 1 1  这里的高位是存在two中,低位存在one中,根据不同状态去做操作;同时为1则清0. 再强调一下,这里one表示的每一位在低位的计数表示,two表示每一位在高位的计数表示;

public:
    int singleNumber(int A[], int n) {
        int one = 0, two = 0, three = 0;
        for (int i = 0; i < n; i++){
            two |= one & A[i];      //be careful
            one ^= A[i];
            three = one & two;
            one &= ~three;
            two &= ~three;
        }
        return one;
    }

这里be careful   two可以用异或,因为不可能出现one two在相同位同时为1的情况,所以异或和或是一样的,但是逻辑上,应该是选用或 ,更能表现这个算法的意思;