【剑指offer】73. 数组中只出现一次的两个数字（超详解）

题目链接

acwing
leetcode

题目描述

给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。 示例 2：

输入：nums = [-1,0]
输出：[-1,0] 示例 3：

输入：nums = [0,1]
输出：[1,0]

分析

1. 常量额外空间——不能使用哈希Map
2. 线性时间复杂度——不能先排序再做

异或！

性质：异或运算：相同为0，不同为1

1 ⊕ 1 = 0
0 ⊕ 0 = 0
1 ⊕ 0 = 1
0 ⊕ 1 = 1

异或运算性质

1. 任何数和0做异或运算，结果仍然是原来的数：a⊕0=a
2. 任何数和其自身做异或运算，结果是0：a⊕a=0
3. 异或运算满足交换律和结合律

简单版本题目-只出现一次的数字

leetcode
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

class Solution {
    public int singleNumber(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num;
        }
        return single;
    }
}

本题思路

假设结果为a和b

1. nums中的所有数字进行异或，得到了的结果为total = a^b（a异或b）
2. total肯定不为0，即至少有一位为1，因为a与b不相等。可以根据total中不为0的位count，将a与b进行区分
3. 遍历整个数组，将数组分为两部分
   1. count位为0的
   2. count位为1的
4. 分别在这两部分中进行异或，就可以得到a和b

因为：
（1）a和b的第count位一个为0一个为1
（2）数组分成两部分之后，这两部分中分别含有a和b，其他的元素肯定是双数个的（两个相同的元素，在某个位置是0还是1是确定的），只有a和b是单数个

代码实现

class Solution {
    public int[] findNumsAppearOnce(int[] nums) {
        // 1. 所有数字异或
        int total = 0;//存储所有数字异或的结果，且任何数字与0异或为本身，所以这样初始化
        for(int num : nums){
            total = total ^ num;
        }
        
        // 2. 判断两个数字第几位不同(total中第几位为1)
        int count = 0;//记录不同的位数
        // int一共32位
        for(int i = 0; i < 32; i ++){
            // 判断total的第i位是否为1，total向右移动i位（相当于去掉了最低的i位）
            if((total >> i & 1) == 1){
                count = i;// 第i位为1
                break;
            }
        }
        
        // 3. 将数组【依据第count位是否为1】分为两部分（这两部分中分别包含了第一个数字 和 第二个数字）
        // 然后对这两部分分别进行异或，得到答案
        int result1 = 0;
        int result2 = 0;
        for(int num : nums){
            if((num >> count & 1) == 1)    result1 = result1 ^ num;
            else result2 = result2 ^ num;
        }
        
        int[] res = {result1, result2};
        return res;
    }
}