只出现一次的数字3

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

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

示例 1：

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

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

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

提示：

2 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
除两个只出现一次的整数外，nums 中的其他数字都出现两次

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/single-number-iii

基本概念：

1 .一个数异或0，还是它本身。
2.一个数异或它本身为0

先不做题，描述下思路：

1.最初想到的解法为空间复杂度为O(n)，借助Map的方式。已经实现过了多次，就不赘述

2.思考空间复杂度为O（1）的解法：

由于我们之前做过一个数组中存在1个1次的数字，那么我们知道所有数字的异或的结果为：存在1个1次的数字。

那么假设知道此题目的最后两个数字是 a、b，那么结果是a^b

而异或是二进制不同的才会为1。

class Solution {
    public int[] singleNumber(int[] nums) {

        //  记录异或结果
        int xor = nums[0];
        for(int i = 1; i < nums.length ; i++){
            xor = xor ^ nums[i];
        }

        //假如设这两个数字为a\b，也就是 a^ b = xor
        
        //观察xor的二进制，找到随机一个k位，如果k位的值为1，那么说明a 、b在这个位置的值是不一样的
        int k = 0;

        for(int i = 1; i < 32;i++){
            if(((xor >> i) & 1) == 1){
                k = i;
                break;
            }
        }

        //找到这个k位置之后，说明 a ^ b的k位置肯定是1，那么我们可以知道a ^ b 在k的位置肯定是不同的
        //那么我们是否可以将num数组中 k 位置 = 1的分为 1组，k位置 不等于1的分为1组，就应该是a 和 b了
        int[] result = new int[2];
        for(int num : nums){
            if(((num >> k) & 1) == 1){
                result[0] = result[0] ^ num;
            } else {
                result[1] = result[1] ^ num;
            }
        }
        return result;


    }
}

时间复杂度为O(n)，空间复杂度O(1)

本题没有想出来，还是通过答案看出来的，失败，看明白答案之后发现并不是特别困难，主要还是有没有这个思路的问题。

加油!