[数据结构与算法]剑指offer 数组中数字出现的次数

前言

剑指offer的第56-I 题，看了LeetCode的官方题解后才写出来，在记录一下写题时的思路以及看答案的困惑之处

一、题目表述

一个整型数组 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]

二、解题思路

解题的思路来自于LeetCode的官方题解，即分组异或的办法。将数组的元素分为两组，分别异或得到只出现一次的数，分组有两个条件需要满足，即

• 两个只出现一次的数要在不同的组
• 出现两次的元素，重复的数必须分在同一组，以保证改组异或的结果为只出现过一次的数

设在数组中只出现了一次的两个数字为$x$ 和 $y$,其他元素都出现了两次，那么数组中所有元素异或的结果就等于$x$ 和 $y$相异或的结果，不妨将其记为$target\_xor$，$target\_xor$除了是$x$ 和$y$异或的结果以外，还有更多的信息。将$target\_xor$写成二进制表示时，则其为0的位，$x$ 和 $y$的对应位相同，为1的位，则$x$ 和 $y$的对应位不同。
我们可以以这个为线索来分组，由于$target\_xor$为1的位表示了$x$ 和 $y$的不同，所以我们以最低位的1来将所有的元素分离。即假设$target\_xor$的倒数第3为1， 我们即可以将所有倒数第三位为1的数分为一组，将所有倒数第三位为1的数分为另一组。这样的分法可以同时满足上述的两个条件。首先由于$target\_xor$的倒数第3为1，说明$x$ 和 $y$的倒数第3位不同，必然一个为1，另一个为0可以分开。另外其他的元素时重复出现的，那么一个数的倒数第32位为1或0，则与其相等的元素也必然如此。由此我们便将数组分为了两部分，每一部分都含有一个只出现了一次的数和若干对出现过两次的数，对这两部分分别异或，即可以找出我们想要找到的那两个数来。

解题代码

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
		int target_xor = 0;
		for(int n : nums)
			target_xor ^= n;
		int divide = 1;
		// 找到最低位的1
		while((divide & target_xor) == 0)
			divide <<= 1;
			
		int ans_a = 0, ans_b = 0;
		for(int n : nums) {
			// 对应位置为1的分到一组
			if(divide & n)
				ans_a ^= n;
			else//对应位置不为1的分到一组
				ans_b ^= n;
		}
		return {ans_a, ans_b};
    }
};