137. 只出现一次的数字 II

137. 只出现一次的数字 II

/*
该题有多种解题思路，比如：1. 统计每个数字出现的次数，然后找出只出现1次的数字，缺点：需要借助辅助空间2. 对数据进行排序，然后找出只出现1次的数字，缺点：时间复杂度不是O(N)
而题目要求了，时间复杂度必须为O(N)线性时间复杂度，因此便增加了题目的难度。题目说：只有一个数字出现一次，其余数字均出现3次，假设数组为{3,5,3,3}
通过分析可知：
3的二进制：0 0 0 0 0 0 1 1
5的二进制：0 0 0 0 0 1 0 1
3的二进制：0 0 0 0 0 0 1 1
3的二进制：0 0 0 0 0 0 1 10 0 0 0 0 1 3 4  二进制1的总数
对于出现3次的数字，各位出现的次数都是3的倍数，因此对统计的为1的比特总数%30 0 0 0 0 1 0 1 = 5结果就是只出现一次的数字
*/// 时间复杂度：O(32*N)--->O(N)  空间复杂度：O(1)
class Solution {
public:int singleNumber(vector<int>& nums) {int ans = 0;for (int i = 0; i < 32; ++i) {// 统计该每个数字第i个比特位为1的总数int total = 0;for (int num: nums) {total += ((num >> i) & 1);}// 如果total能够被3整除，说明只出现一次的数字在该位置上一定是0// 否则在该位置上一定是1if (total % 3) {ans |= (1 << i);}}return ans;}
};

该题还有更简单的解决方式，不过不太容易理解，请兴趣同学可以参考下底下处理方式：

https://leetcode.cn/problems/single-number-ii/solution/zhi-chu-xian-yi-ci-de-shu-zi-ii-by-leetc-23t6/