剑指Offer_56_数组中数字出现的次数

题目1描述：

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

示例：

输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]

限制：2 <= nums.length <= 10000

解法1：异或运算

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {

        int x = 0, y = 0, n = 0, m = 1;

        //异或运算有个重要的性质：两个相同数字异或为0，
        //因此，若将nums中所有数字执行异或运算，留下的结果则为出现一次的数字
        for (int num : nums) n ^= num;

        //本题难点：数组nums有两个只出现一次的数字，因此无法通过异或直接得到这两个数字
        //nums = [1,2,10,4,1,4,3,3] 异或后的n为1000
        //循环左移，计算m的值为8，1000
        while ((n & m) == 0) m <<= 1;

        //所以根据第4位是否为1将原数组分为两个子数组
        //[10]、[1,2,4,1,4,3,3]
        //分别进行异或计算
        for (int num : nums) {       

            if ((num & m) != 0) x ^= num;  //第4位为1
            else y ^= num;  //第4位不为1
        }

        return vector<int> {x, y};  //返回只出现一次的数字
    }
};

❗️LeetCode_137_只出现一次的数字2

题目2描述：

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

示例：

输入：nums = [3,4,3,3]
输出：4

输入：nums = [9,1,7,9,7,9,7]
输出：1

限制：
1. 1 <= nums.length <= 10000
2. 1 <= nums[i] < 2^31

解法1：哈希表

class Solution {
public:
    int singleNumber(vector<int>& nums) {

        unordered_map<int,int> map;  //定义一个哈希表

        for (int i = 0;i < nums.size();++i) ++map[nums[i]];
        //for (auto &i : nums) ++map[i];

        for (auto &v : map) {

            if (v.second == 1) return v.first;
        }

        return NULL;
    }
};