本文共 1238 字，大约阅读时间需要 4 分钟。

Single Number II

Total Accepted: 44725 Total Submissions: 128964

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?

这个题目是，给定一个序列，所有的数字都出现三次，只有一个出现一次，找出这个数字。 如果是出现两次的话，我们可以使用异或，异或两次就是0了，然后剩余的就是那个单独的数字。

如果是出现三次的话，我们可以这样实现：我们用一个32容量的数组储存当前位置，bit1出现的次数。最后的时候我们把每个次数模3，这样出现3次的就被模为0了。 例如： 3组数字 1 0 0 0 1 0 1 0 0 1 0 0 把所有1加起来，运算的结果是 3 1 0 我们把各位模3结果就是0 1 0即是，单独的数字。 最后把这个数字转换成数字即可，但是需要注意，如果最高位是1的话，也就是负数，需要取反再加一。

class Solution {public:    int singleNumber(int A[], int n) {        vector
   
     bitMod3(32, 0);        int result = 0;        for(int i = 0; i < n; ++i)        {            for(int j = 0; j < 32; ++j)            {                if(A[i] >> j & 1 == 1)                    bitMod3[j]++;            }        }        for_each(bitMod3.begin(), bitMod3.end(), [](int &x)        {            x %= 3;        });         for(int i = 0; i < 32; ++i)        {            if(bitMod3[i] ^ bitMod3[31]) //如果是负数各位取反                result += pow(2, i);        }        if(bitMod3[31])        {            ++result;            result = -result;        }        return result;    }};
   

转载地址：http://djezb.baihongyu.com/