首页 > 代码库 > LeetCode:Single Number(2)

LeetCode:Single Number(2)

问题描述:

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?

思路:将数组中的每一个元素的每一位相加,然后mod 3。得到的就是要求的数相应位上的元素。最后再将32个位组合,既得要求的数。


代码:

int Solution::singleNumber(int A[], int n)
{
    int bits[32] = {0};
    int sum;
    for(int i = 0;i < 32;i++){
        sum = 0;
        for(int j = 0;j < n;j++){
        if((A[j] >> i) & 1 != 0)
            sum = sum + 1;
        }
        bits[i] = sum % 3;
    }
    int num = 0;
    int x = 1;
    for(int i = 0;i < 32;i++){
        num = num + bits[i] * x;
        x = x * 2;
    }
    return num;
}


LeetCode:Single Number(2)