137.Single Number II
难度: Medium
刷题内容
原题连接 * https://leetcode.com/problems/single-number-ii/
内容描述 ``` Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2,2,3,2] Output: 3 Example 2:
Input: [0,1,0,1,0,1,99] Output: 99 ```
解题方案
思路
相同的数有相同的二进制，相同位置有相同的1，0；所以如果都出现3次，那么相同位上出现的1和0都是3的倍数
所以，统计不同位上1、0的个数，如果不是3的倍数，说明出现次数不是3的倍数。
所有不为3倍数的位加起来就是结果。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int arr[32][2],t = 0;
memset(arr,0,sizeof(arr));
for(int i = 0;i < nums.size();++i)
{
int count1 = 0;
long long temp = nums[i];
if(nums[i] < 0)
{
t++;
temp *= -1;
}
while(temp)
{
arr[count1++][temp % 2]++;
temp /= 2;
}
}
int ans = 0;
for(int i = 0;i < 32;++i)
if(arr[i][1] % 3)
ans += pow(2,i);
if(t % 3)
ans *= -1;
return ans;
}
};
