剑指 Offer II 004. 只出现一次的数字
难度中等52收藏分享切换为英文接收动态反馈
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
示例 1：
输入：nums = [2,2,3,2]
输出：3
示例 2：
输入：nums = [0,1,0,1,0,1,100]
输出：100
提示：
1 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
题目思路：
这道题的思路总的来说很简答，就是将每个数变成二进制的，这么来说，数组中的所有数都变成二进制的参与本程序的运算，
对于每个数来说，不管是什么数当他变成二进制之后他的每一位不是0就是1，我们对数组中每个数变成二进制之后的每一位
进行求和，然后对3进行取余，就会得到单独出现的那位数，（因为其他的数都是出现三次的，所有对3取余之后都为0，多出来
的那个就是只出现一次的），如果这个数位1，则将1移动到i位置上，与a进行或运算，相当于在i位上赋1，如果是0则不用管
因为在移动过程中会对没有运算的地方自动补0.
python代码：
class Solution: def singleNumber(self, nums: List[int]) -> int: ans = 0 #构建变量a = 0 for i in range(32): #遍历32位数，因为所有数转换为二进制的话，一共可有32位 total = sum((num >> i) & 1 for num in nums) #定义个整数来存储数组的某位的数相加的和,所有数的某位数相加 得到all if total % 3: #如果all%3 为0，则不进行如下操作，直接跳入下一个循环，因为当前补0即可 if i == 31: #/如果all%3 为0，则不进行如下操作，直接跳入下一个循环，因为当前补0即可 ans = ans - (1 << i) #因为python对有符号数和无符号数没有区分，因此我们这里需要进行31位的判断 else: ans = ans | (1 << i) #如果为1的话，则需要将1位移到相应的位置，然后与a进行或运算，即在a的i位上赋值1 return ans
C++代码：
class Solution { public: int singleNumber(vector<int>& nums) { int a = 0; //构建变量a = 0 for (int i = 0; i < 32; i++){ //遍历32位数，因为所有数转换为二进制的话，一共可有32位 int all = 0; //定义个整数来存储数组的某位的数相加的和 for (int num: nums){ all += (num>>i)&1; //所有数的某位数相加 得到all } if (all%3){ //如果all%3 为0，则不进行如下操作，直接跳入下一个循环，因为当前补0即可 a |= 1<<i; //如果为1的话，则需要将1位移到相应的位置，然后与a进行或运算，即在a的i位上赋值1 } } return a; //输出答案 } };
