剑指 Offer 56 - I. 数组中数字出现的次数
难度中等630收藏分享切换为英文接收动态反馈
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
示例 2：
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
限制：
2 <= nums.length <= 10000
通过次数153,689提交次数221,806
解题思路：
相同的数字异或为0，不同的数字异或为1，0异或任何数字为数字自身，本着这个原则，我们可以进行这道题的学习，
第一步：我们将整个数组的数都与0进行异或，我们就可以得到两个不同的数字，设为a ， b，即a和b异或的值。
第二步：因为相同的数字异或为0，不同的数字异或为1，因此我们找到a和b异或值中第一个为1的位置m
第三步：我们将m与全数组的值进行与，构建两个子数组这样可以将两个不同的值a和b分在不同的数组，且相同的值与
m与的值一定相同，我们把他分在相同的组，将两个组的值进行异或，即可得到a和b的值。
Python代码：
class Solution: def singleNumbers(self, nums: List[int]) -> List[int]: a , m , x , y= 0 , 1 , 0 , 0 #相同的数字异或为0，0异或任何数字为数字自身 for i in nums:a = a^i #数组全部异或，求出只出现两个数字的异或值 while a&m==0 : m<<=1 #判断第一次出现1的地方 for i in nums:#遍历数组 if i&m: x ^= i#根据跟与m的情况，可以将 两个不同的值分到两个不同的组进行异或 else: y ^= i#相同的值跟m与的情况一定是相同的，因此可以将相同的值分到同一组，不同的值分到不同的组 return [x, y]
C++代码：
class Solution { public: vector<int> singleNumbers(vector<int>& nums) { int a=0 , m=1 , x=0 , y=0; for(auto &i: nums) a ^= i;//遍历异或 while ((a&m)==0) m <<= 1; //寻找第一个为1的地方m for(auto &j: nums){ if (j&m) x^=j; //将数组分为两个子数组分别进行异或 else y^=j; } return {x , y}; } };
