数组中数字出现的次数

题目描述

一个整型数组 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

题目链接

Leetcode

题目解答

解法一

Set去重，遍历数组，把元素添加到Set中，如果添加失败说明元素已存在，需要把该元素剔除掉，Set中剩余的元素就是两个只出现一次的数字。

时间复杂度:$O(n)$ 空间复杂度:$O(1)$

class Solution {
    public int[] singleNumbers(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int[] res = new int[2];
        for (int num : nums) {
            if (!set.add(num)) {
                set.remove(num);
            }
        }
        int index = 0;
        for (int num : set) {
            res[index++] = num;
        }
        return res;
    }
}

执行用时：10 ms, 在所有 Java 提交中击败了15.71%的用户
内存消耗：39.7 MB, 在所有 Java 提交中击败了96.45%的用户

解法二

1
2
3

a ^ a = 0; // 相同的两个数异或值为0
a ^ 0 = a; // 一个数与0异或值为自身
a ^ b ^ c = a ^ c ^ b; // 异或具有交换律

分组异或，根据异或的性质，先对所有元素进行异或操作，得到的结果就是两个只出现一次数字的异或值res，然后我们取这个值二进制中最低位1所表示的值div，把数组中每个元素与div进行与运算得到的结果作为分组依据。这个最低位1所在的位置是两个只出现一次的数字二进制中最低的不相等的位，通过和这个位的与运算可以把这两个数字区分开，同时对于其他元素来说，如果两个元素是相等的，那么一定会被分到同一个组，最终两个分组中元素异或完的值就都是只出现一次的数字。

时间复杂度:$O(n)$ 空间复杂度:$O(1)$

class Solution {
    public int[] singleNumbers(int[] nums) {
        int res = 0;
        for (int num : nums) {
            res ^= num;
        }
        int div = 1;
        while ((div & res) == 0) {
            div <<= 1;
        }
        int a = 0, b = 0;
        for (int num : nums) {
            if ((num & div) == 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }
        return new int[]{a, b};
    }
}

执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：39.9 MB, 在所有 Java 提交中击败了90.13%的用户