1.题目介绍

2.题解

2.1 快排+遍历

思路

同本系列前几题一样

代码

class Solution {
public:
    std::vector<int> singleNumber(std::vector<int>& nums) {
        int count = 0;
        std::vector<int> arr;
        std::sort(nums.begin(),nums.end());
        for (int i = 0; i < nums.size(); i++) {
            if (i == nums.size() - 1 && count == 0) {
                arr.push_back(nums[i]);
                if (arr.size() == 2) return arr;
            };
            if (nums[i] == nums[i+1]) count++;
            else if(count) count = 0;
            else {
                arr.push_back(nums[i]);
                if (arr.size() == 2) return arr;
            }
        }
        return arr;
    }
};

复杂度分析

• 时间复杂度：
  排序阶段的时间复杂度为 \(O(nlog_n)\)，其中 n 是输入数组的长度。
  查找单独出现数字的阶段是一个线性扫描，时间复杂度为 O(n)。
  总体来说，代码的时间复杂度为 \(O(nlog_n) + O(n) = O(nlog_n)\)。

• 空间复杂度：
  代码的空间复杂度为 O(1)。

2.2 哈希表（牺牲空间）

思路

设计（数字，出现次数）的键值对，使用哈希表进行存储

代码

class Solution {
public:
    std::vector<int> singleNumber(std::vector<int>& nums) {
        std::vector<int> arr;
        std::unordered_map<int, int> map;
        for (int num: nums){
            map[num]++;
        }
        for (const auto& [num, occ]: map){
            if (occ == 1) arr.push_back(num);
        }
        return arr;
    }
};

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 nums的长度。
• 空间复杂度：O(n)，即为哈希映射需要使用的空间。

2.3 位运算（分治算法）

思路

假设数组 nums 中只出现一次的元素分别是x1和x2，如果把 nums中的所有元素全部异或起来，得到结果 x，那么一定有：\(x=x_1\oplus x_2\)

x显然不会等于 0,因为如果 \(x=0\) , 那么说明 \(x_1=x_2\) ,这样 \(x_1\) 和 \(x_2\) 就不是只出现一次的数字了。因此,我们可以使用位运算 \(x \& -x\) 取出 \(x\) 的二进制表示中最低位那个 1, 设其为第\(l\) 位, 那么 \(x_1\) 和 \(x_2\) 中的某一个数的二进制表示的第 \(l\) 位为 0, 另一个数的二进制表示的第 \(l\) 位为 1。在这种情况下, \(x_1\oplus x_2\) 的二进制表示的第 \(l\) 位才能为 1。

这样一来,我们就可以把 \({nums}\) 中的所有元素分成两类,其中一类包含所有二进制表示的第 \(l\)位为 0 的数, 另一类包含所有二进制表示的第 \(l\) 位为 1 的数。可以发现:

• 对于任意一个在数组 \(nums\) 中出现两次的元素, 该元素的两次出现会被包含在同一类中;
• 对于任意一个在数组 \(nums\) 中只出现了一次的元素, 即 \(x_1\) 和 \(x_2\), 它们会被包含在不同类中。

这里其实就是一种分治算法的思想