题目内容

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

算法应该具有线性时间复杂度。 不使用额外空间来实现.

示例

示例 1：

输入：nums = [2,2,3,2]
输出：3

示例 2：

输入：nums = [0,1,0,1,0,1,99]
输出：99

提示

1、1 <= nums.length <= 3 * 10^4
2、-2^31 <= nums[i] <= 2^31 - 1
3、nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

题解

本题依旧采用位运算的方式求解。但是求解思路与上一题有不同的地方。思考一下本题的特点，除了一个数之外，其余的数都有三个。因此，32位的int值中，针对每一位，求数组中的数对应该位上的1的和与0的和。那么我们可以思考有什么特点，就是说当出现一次的那个数，对应位为1，那么在针对该位为1的求和数量上，应该是3的倍数+1个；如果对应位为0，那么在针对该位为0的求和数量上，应该是3的倍数+1个。因此根据这个特点，我们可以一位一位的确定仅出现一次的那个数32位的0和1的二进制表示，再转化为十进制表示即可。

代码

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int bit = 0; bit < 32; bit++) {
            int counter = 0;//求和标识位
            for (int i = 0; i < nums.size(); i++)
                counter += (nums[i] >> bit) & 1;//求每一位上，1的个数
            ans += (counter % 3) << bit;//如果1的个数模3：结果为0，则说明对应答案那一位是0；结果为1，则说明对应答案那一位为1。然后左移到bit个位上即可。这里相当于直接左移的同时处理了二进制转10进制的问题，答案直接就是十进制。
        }
        return ans;
    }
};