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

[LeetCode] Single Number II

2024-07-09 23:55:48   215人阅读

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?

 

方法一：创建一个长度为 多少个bit/sizeof(int) * 8的数组 count[sizeof(int)*8]，count[i] 表示在在 i 位
出现的 1 的次数。如果 count[i] 是 3 的整数倍，则忽略；否则就把该位取出来组成答案。

 

 1 class Solution 2 { 3     public: 4         int singleNumber(int A[], int n) 5         { 6             vector<int> cnt; 7             int width = sizeof(int)*8; 8             cnt.resize(width, 0); 9             int res = 0;10 11             for(int i  = 0; i< n; i++)12             {13                 for(int j  = 0; j< width; j++)14                 {15                     cnt[j] += (A[i] >> j) & 0x1;16                     //cnt[j] %= 3;17                 }18 19             }20             for(int j  = 0; j< width; j++)21             {22                 //cout << "j :\t" <<j <<"\t cnt\t"<< cnt[j]<<endl;23                 if(cnt[j]%3 != 0)24                     res ^=  ( 1 << j);25             }26             return res;27         }28 } ;

 


联系
我们