83 落单的数 II

原题网址：http://www.lintcode.com/zh-cn/problem/single-number-ii/

给出3*n + 1 个的数字，除其中一个数字之外其他每个数字均出现三次，找到这个数字。

您在真实的面试中是否遇到过这个题？ 

Yes

样例

给出 [1,1,2,3,3,3,2,2,4,1] ，返回 4

挑战 

一次遍历，常数级的额外空间复杂度

标签 

贪心

 

非挑战版AC代码：

思路依旧是先排序，再遍历。每隔两个数（每三个数）做一次减法，若差值不为零返回被减数，一直遍历到第n-1个数，若一直无输出，说明最后一个元素是落单的数，将该值return出去。

 

class Solution {
public:
    /**
     * @param A: An integer array
     * @return: An integer
     */
    int singleNumberII(vector<int> &A) {
        // write your code here
        if (A.empty())
    {
        return NULL;
    }
    int size=A.size();
    sort(A.begin(),A.end());
    for (int i=0;i<size-1;i+=3)
    {
        if (A[i]-A[i+1]!=0)
        {
            return A[i];
        }
    }
    return A[size-1];
    }
};

挑战：一次遍历，常数级的额外空间复杂度

参考： https://blog.csdn.net/wangyuquanliuli/article/details/46637377

           https://blog.csdn.net/zaqwsx20/article/details/52823538?utm_source=itdadao&utm_medium=referral

           C++中位运算的使用方法

位操作，统计所有数字各个位上数字的和，除以3取余就是落单数在这个位上的值。

class Solution {
public:
    /**
     * @param A: An integer array
     * @return: An integer
     */
    int singleNumberII(vector<int> &A) {
        // write your code here
         int buf[32]={0}; //int类型32个位;
     for (int i=0;i<(int)A.size();i++) //计算数组中所有元素各个位的和(二进制),存放在数组buf中;
     {
         addBuf(A[i],buf);
     }
     int result=0;
     for (int j=0;j<32;j++)
     {
         int val=buf[j]%3;  //各个位的和对3取余数,val值非0即1;
         result=(val<<j|result);  //由数组恢复成整数(注意是二进制运算)，j是第几位，所以需要左移j;
     }                                      //或运算保证之前的结果不丢失;
     return result;
    }
    
    void addBuf(int x,int *buf)
{
    for (int i=0;i<32;i++)
    {
        buf[i]=buf[i]+(x>>i&1);
    }
}
};