260. 只出现一次的数字 III(中等)

1，问题描述

260. 只出现一次的数字 III

难度：中等

给你一个整数数组 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 中的其他数字都出现两次

2，初步思考

​ 这个题目有时间复杂度、空间复杂度要求，所以会是一道中等难度的题目
​ 只有通过位运算才能降低复杂度

3，代码处理

import java.util.HashSet;
import java.util.Set;

public class _260只出现一次的数字III {

    // 你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
    // 翻译一下：时间复杂度O（n），空间复杂度O（1）

    // 解法：位运算,2个不同的数字，异或结果肯定不为0，一定有某些位上不同时为1或者0
    // 通过某些位上不同时为1或者0这个特性，将他们区分开来
    public int[] singleNumber_bit(int[] nums) {
        int xor = 0;
        for (int num : nums) {
            xor ^= num;
        }

        // 获取最低位1
        int lowbit = xor == Integer.MAX_VALUE ? Integer.MAX_VALUE : xor & (-xor);
//        while ((xor & lowbit) == 0) {
//            lowbit <<= 1;
//        }

        int a = 0, b = 0;
        for (int num : nums) {
            if ((num & lowbit) == 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }
        return new int[]{a, b};
    }

    // 解法：hash表缓存
    public int[] singleNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (set.contains(num)) {
                set.remove(num);
            } else {
                set.add(num);
            }
        }
        int[] res = new int[2];
        int idx = 0;
        for (Integer i : set) {
            res[idx++] = i;
        }
        return res;
    }

    public static void main(String[] args) {
//        _260只出现一次的数字III onlyOne = new _260只出现一次的数字III();
//        System.out.println(onlyOne.singleNumber(new int[]{1, 2, 1,}));

        System.out.println(Integer.toBinaryString(4));
        System.out.println(Integer.toBinaryString(-4));
        System.out.println(Integer.toBinaryString(-4 & 4));

    }


}
// 如果没有限制的话
// 解法1:排序后比较，时间复杂度O（nlogn），空间复杂度O（1）
// 解法2:使用哈希表，时间复杂度O（n），空间复杂度O（n）