首页 > 代码库 > [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?

思路:

(所有数的第i位之和)mod 3 = (查找的数的第i位),其中 i = 1,2,...,sizeof(int)*8。

如下算法:如果在你的机器上int是32位,则时间复杂度是O(32n),即线性时间,空间复杂度O(1)

注:

一个数与1(000001)相与得到此数最末位;

一个数与2(000010)相与得到此数次末位;

依次类推,即一个数与相应权重相与得到此数在本权重位的值。

class Solution {
public:
    int singleNumber(int A[], int n) {
        
        int bits = sizeof(int)*8;
        int weight = 1,result=0;

        for(int i =0;i<bits;i++)
        {
           int sum = 0;
           for(int j=0;j<n;j++)
           {
           
             sum += (A[j] & weight)/weight;  // 每个数与权值weight相与得到这个数在权值位上的值,比如weight=2,本句sum得到所有数第2位之和。
           
           }
           result += (sum % 3)*weight; //sum % 3得到要查找的数的权值位的值,再乘权值,就是查找数在权值位代表的真实值。
           weight *= 2;
        
        }

        return result;
    }
};