剑指Offer【数组中数字出现的次数】

题目描述

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

示例 1：

1 2	`输入：nums = [4,1,4,6] 输出：[1,6] 或 [6,1]`

示例 2：

1 2	`输入：nums = [1,2,10,4,1,4,3,3] 输出：[2,10] 或 [10,2]`

限制：

2 <= nums.length <= 10000

解法

位运算
- 相同的数异或为0，不同的异或为1。0和任何数异或等于这个数本身。
- 所以，数组里面所有数异或 = 目标两个数异或。由于这两个数不同，所以异或结果必然不为0。
- 假设数组异或的二进制结果为10010，那么说明这两个数从右向左数第2位是不同的
- 那么可以根据数组里面所有数的第二位为0或者1将数组划分为2个。
- 这样做可以将目标数必然分散在不同的数组中，而且相同的数必然落在同一个数组中。
- 这两个数组里面的数各自进行异或，得到的结果就是答案

class Solution {
    public int[] singleNumbers(int[] nums) {
        int[] res= new int[2];
        int x=0,y=0,n=0,m=1;
        //1.全数组进行异或得到两个不同数异或的结果x⊕y
        for (int num : nums) {
            n^=num;
        }
        //2.从右往左计算x,y第一位不相同的数
        while ((n&m)==0){
            m<<=1;
        }
        //3.根据m进行分组异或，得到x，y为结果
        for (int num : nums) {
            if ((num&m)==0){
                x^=num;
            }else {
                y^=num;
            }
        }
        res[0]=x;
        res[1]=y;
        return res;
    }
}