lintcode-83-落单的数 II

83-落单的数 II

思路

利用位运算，int有32位，用一个长度为32的数组记录每个数字的所有位中1出现的次数，如果这个数字出现3次，则与这个数字对应的每一位上的1也出现三次。最后将数组每一位均对3取余，最后得到的就是要求的数字。

code

class Solution {

public:

	/**

	 * @param A : An integer array

	 * @return : An integer

	 */

    int singleNumberII(vector<int> &A) {

        // write your code here

        int bits[32] = {0};

        int size = A.size(), i = 0, j = 0, result = 0;

        if(size <= 0) {

            return 0;

        }

        for(i=0; i<32; i++) {

            for(j=0; j<size; j++) {

                bits[i] += A[j]>>i & 0x00000001;

            }

            bits[i] = bits[i] % 3;

            result = result | bits[i] << i;

        }

        return result;

    }

};