剑指 Offer 56 - I. 数组中数字出现的次数

描述

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

链接

 剑指 Offer 56 - I. 数组中数字出现的次数 - 力扣（LeetCode） (leetcode-cn.com)

解法：

本题难点： 数组 numsnums 有 两个 只出现一次的数字，因此无法通过异或直接得到这两个数字。

设两个只出现一次的数字为 x , y ，由于 x =y ，则 x 和 y 二进制至少有一位不同（即分别为0 和 1 ），根据此位可以将nums 拆分为分别包含 x 和 y 的两个子数组。

^是异或运算符，异或的规则是转换成二进制比较，相同为0，不同为1.

(9条消息) Java中的异或运算符^_keepon的博客-CSDN博客_java异或

 1 class Solution {
 2     public int[] singleNumbers(int[] nums) {
 3         // 将数组 nums 拆分为 左x、右y 两个数组
 4         int  x = 0, y = 0, tmp = 0, BaseValue = 1;
 5         // 1、遍历 异或
 6         for (int num : nums)
 7             tmp ^= num;
 8         // 2、 循环 左移， 计算 两个数 具体在 哪一位上 不一样
 9         while ((tmp & BaseValue) == 0)
10             BaseValue <<= 1;
11         // 3、 遍历nums分组，分为 ==0 和 ！=0
12         for (int num : nums) {
13             if ((num & BaseValue) != 0)
14                 x ^= num;
15             else
16                 y ^= num;
17         }
18         // 4、返回 出现一次 的数字
19         return new int[] {x, y};
20     }
21 }

参考

数组中数字出现的次数 - 力扣（LeetCode） (leetcode-cn.com)