Skip to content

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


回到顶部