首页 > 代码库 > [LeetCode] Single Number II

[LeetCode] Single Number II

2024-07-07 18:56:31   226人阅读

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;
    }
};

 

 


联系
我们