LC 260. 只出现一次的数字 III

题目描述

这是 LeetCode 上的 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 \times 10^4$

• $-2^{31} <= nums[i] <= 2^{31} - 1$

• 除两个只出现一次的整数外，nums 中的其他数字都出现两次

进阶：你的算法应该具有线性时间复杂度，你能否仅使用常数空间复杂度来实现？

---

哈希表

朴素的做法是利用哈希表进行统计，最后将统计次数为 $1$ 的元素加入答案。

Java 代码：

class Solution {
    public int[] singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : nums) map.put(i, map.getOrDefault(i, 0) + 1);
        int[] ans = new int[2];
        int idx = 0;
        for (int i : nums) {
            if (map.get(i) == 1) ans[idx++] = i;
        }
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        unordered_map<int, int> cmap;
        for (int num : nums) cmap[num]++;
        vector<int> ans;
        for (int num : nums) {
            if (cmap[num] == 1) ans.push_back(num);
        }
        return ans;
    }
};

Python 代码：

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        count_map = Counter(nums)
        return [num for num in nums if count_map[num] == 1]

TypeScript 代码：

function singleNumber(nums: number[]): number[] {
    const countMap: Map<number, number> = new Map();
    for (const num of nums) countMap.set(num, (countMap.get(num) || 0) + 1);
    const ans: number[] = [];
    for (const num of nums) {
        if (countMap.get(num) === 1) ans.push(num);
    }
    return ans;
};

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

---

异或

利用除答案以外的元素均出现两次，我们可以先对 $nums$ 中的所有元素执行异或操作，得到 $sum$，$sum$ 为两答案的异或值（$sum$ 必然不为 $0$）。

然后取 $sum$ 二进制表示中为 $1$ 的任意一位 $k$，$sum$ 中的第 $k$ 位为 $1$ 意味着两答案的第 $k$ 位二进制表示不同。

对 $nums$ 进行遍历，对第 $k$ 位分别为 $0$ 和 $1$ 的元素分别求异或和（两答案必然会被分到不同的组），即为答案。

Java 代码：

class Solution {
    public int[] singleNumber(int[] nums) {
        int sum = 0, k = -1;
        for (int i : nums) sum ^= i;
        for (int i = 31; i >= 0 && k == -1; 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;
    }
}

C++ 代码：

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

Python 代码：

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        sum_val, k = 0, -1
        for num in nums: sum_val ^= num
        for i in range(31, -1, -1):
            if (sum_val >> i) & 1:
                k = i
                break
        ans = [0, 0]
        for num in nums:
            if (num >> k) & 1: ans[1] ^= num
            else: ans[0] ^= num
        return ans

TypeScript 代码：

function singleNumber(nums: number[]): number[] {
    let sum = 0, k = -1;
    for (const num of nums) sum ^= num;
    for (let i = 31; i >= 0 && k === -1; i--) {
        if (((sum >> i) & 1) === 1) k = i;
    }
    const ans: number[] = [0, 0];
    for (const num of nums) {
        if (((num >> k) & 1) === 1) ans[1] ^= num;
        else ans[0] ^= num;
    }
    return ans;
};

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

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.260 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。