0137._Single_Number_II.md

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