260.只出现一次的数字Ⅲ

题目：260.只出现一次的数字Ⅲ

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

示例：

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

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

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

题解：

方法一：哈希集合
对于这种寻找出现次数的题目，可以统一使用哈希表或者哈希集合来做，本题使用哈希集合.
首先遍历整个数组，如果遍历到的数字没有在集合中，就把它加进去，如果已经在了就把他删除。
这样遍历完整个数组，就只剩下了我们需要的只出现一次的两个元素，我们再遍历集合，把集合中的数放到数组中。

public int[] singleNumber(int[] nums) {
    int n = nums.length;
    if (n == 2)
         return nums;
    int[] ans = new int[2];
    Set<Integer> help = new HashSet<>();
    for (int i = 0; i < n; i++) {
        if (help.contains(nums[i]))
            help.remove(nums[i]);
        else
            help.add(nums[i]);
    }
    int i = 0;
    for (int x : help) {
        ans[i++] = x;
    }
    return ans;
}

方法二：
使用位运算异或，首先遍历整个数组进行异或，最后只剩下出现一次的两个数异或的结果sum。
之后我们取sum二进制表示中为1的任意一位k，sum中k位为一就说明只出现一次的这两个数k位是不同的。
之后我们在对nums进行遍历，我们对k位为0和为1的分别进行异或操作（两个答案因为k位不同，所以必定会被分到两个组中），就求出了答案

public int[] singleNumber(int[] nums) {
    int sum = 0;
    for (int i : nums) sum ^= i;
    int k = -1;
    for (int i = 31; i >= 0; i--) {
        if (((sum >> i) & 1) == 1) k = i;
    }
    int[] ans = new int[2];
    for (int i : nums) {
        if (((i >> k) & 1) == 1) ans[1] ^= i;
        else ans[0] ^= i;
    }
    return ans;
}

PS：昨天的每日一题太难了（我不会做，不是），昨天考了近世代数，光复习了没来及的做（还是因为菜）