每日一题--数组中只出现一次的两个数字

题目描述

一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

数据范围

• 数组长度：2 ≤ n ≤ 1000
• 数组元素值：0 < val ≤ 1000000

要求：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

提示

• 输出时按非降序排列。

示例

示例1

输入：

[1,4,1,6]

返回值：

[4,6]

说明：

• 返回的结果中较小的数排在前面。

示例2

输入：

[1,2,3,3,2,9]

返回值：

[1,9]

题解

解题思路

本题要求找出数组中出现一次的两个数字。由于数组中只有两个数字出现一次，其他数字都出现了两次。我们可以利用 位运算 来高效求解。

位运算方法

1. 异或运算：我们可以利用异或（^）的特性来解决这个问题。异或运算有以下特点：

   • a ^ a = 0，即相同的数字异或结果为0；
   • a ^ 0 = a，即任何数字与0异或结果为其本身；
   • 异或运算具有交换律和结合律。

2. 求解步骤：

   • 将数组中的所有数字进行异或。由于其他数字都出现了两次，它们的异或结果为0，最后剩下的就是两个只出现一次的数字的异或结果。
   • 假设这两个只出现一次的数字为 x 和 y，那么 x ^ y 就是一个非0的值。我们可以根据 x ^ y 的二进制表示找到 x 和 y 的不同位。
   • 通过分组操作，将所有数字根据该位进行分组，这样就可以分别找到 x 和 y。

步骤：

1. 对数组中的所有元素进行异或，得到 xor。
2. 找到 xor 中某一位的为1的位置（即 xor 中第一个为1的位置），这表示 x 和 y 在这一位上不同。
3. 根据该位置将所有数字分为两组，分别对每组中的数字异或，得到的结果即为 x 和 y。

代码实现

/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param nums int整型一维数组* @param numsLen int nums数组长度* @return int整型一维数组* @return int* returnSize 返回数组行数*/
int* FindNumsAppearOnce(int* nums, int numsLen, int* returnSize ) {*returnSize = 2;int* result = (int*)malloc(*returnSize * sizeof(int));int xor = 0;for (int i = 0; i < numsLen; i++) {xor ^= nums[i];}int right1 = xor &(-xor);*result = 0;  // 初始化结果数组*(result + 1) = 0;for (int i = 0; i < numsLen; i++) {if ((nums[i]&right1) !=0)*result ^= nums[i];else*(result + 1) ^= nums[i];}if(*(result + 1)<*result){*(result + 1)^=*result;*result^=*(result + 1);*(result + 1)^=*result;}return result;// write code here
}

代码解析

1. 第一步：我们通过对所有数字进行异或得到 xorResult，这个值是两个只出现一次的数字的异或结果。

2. 第二步：我们找到 xorResult 中最低为1的位。通过 xorResult & (-xorResult) 操作，即xorResult & (~xorResult+1) 我们获取到这一位的值。

3. 第三步：根据该位的值将数组中的元素分为两组：

   • 如果该位为1，则将元素分配到一组（在 num1 中异或）；
   • 如果该位为0，则将元素分配到另一组（在 num2 中异或）。

4. 第四步：异或操作后，num1 和 num2 就分别是我们要找的两个只出现一次的数字。

5. 返回结果：最后，我们返回按非降序排列的两个数字。

时间与空间复杂度

• 时间复杂度：O(n)，我们遍历了一遍数组进行异或运算。
• 空间复杂度：O(1)，我们只用了常数空间来存储临时变量。
  要理解为什么 xorResult & (-xorResult)（或者等价的 xorResult & (~xorResult + 1)) 能得到 xorResult 中最低有效的 1 位的值，我们需要从二进制和补码的角度来分析。

按位与操作获取最小位1的原理

xorResult & (-xorResult) 的效果依赖于补码的特性。我们逐步解析这个过程：

• xorResult 中最低有效的 1 位前的所有位都是 0 或者 1，而这个最低有效的 1 位后的所有位都应该是 0。
• -xorResult 是 xorResult 取反再加 1 的结果，它和 xorResult 在最低有效 1 位之前的二进制位完全相反，且在最低有效 1 位后面与 xorResult 的二进制位相同。

让我们举一个具体的例子，假设 xorResult = 12，其二进制表示为：

$$xorResult=00000000000000000000000000001100$$

-xorResult（即 ~xorResult + 1）为：

$$-xorResult=11111111111111111111111111110100$$

然后进行按位与操作：

$$xorResult\&(-xorResult)=00000000000000000000000000001100\&11111111111111111111111111110100=00000000000000000000000000000100$$

得到的结果是：

$$00000000000000000000000000000100$$

这个结果是 4，也就是最低有效 1 位的值。

为什么选择最低有效的 1 位而不是其他位？

最后得到的xor是所有的异或位，a^b,如果最低为为1，说名最低有效的 1 位，是因为它是异或结果中最早出现的差异位，它能够最早地分割数组，使得我们能更快地定位到这两个不同的数字。分割成两组，一组为这位是1和多个出现两次的数，然后，一组为这位是0和多个出现两次的数，多个出现两次的数异或后为0。所以解决