题目描述

题目链接：137. Single Number II

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

You must implement a solution with a linear runtime complexity and use only constant extra space.

例子

例子 1

Input:nums = [2,2,3,2] Output:3

例子 2

Input:nums = [0,1,0,1,0,1,99] Output:99

Constraints

• 1 <= nums.length <= 3 * 10^4
• -2^31 <= nums[i] <= 2^31 - 1
• Each element in nums appears exactly three times except for one element which appears once.

解题思路

这道题比较简单并且在线性时间内的解法是遍历32次数组，每一次计算对应该位中 1 出现的次数，并将其对 3 求余，由于题目规定了每个数字要么出现一次，要么出现3次，所以该位中出现1的次数要么是3的整倍数，要么多出一个1，我们将这个余数放到结果中的对应位置即可。代码如下：

#include <vector>

class Solution {
public:
    int singleNumber(std::vector<int>& nums) {
        int result = 0;
        for (int i = 0; i < 32; ++i) {
            int count = 0;
            for (int num : nums) {
                count += ((num >> i) & 0x1);
            }
            result |= ((count % 3) << i);
        }

        return result;
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(1)

GitHub 代码同步地址： 137.SingleNumberIi.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions