LeetCode 只出现一次的数字 合集

一：只有一个元素出现一次，其他出现两次

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

思路： 利用异或性质，即 a ^ b ^ a = b;

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for(int& i : nums) {
            res ^= i;
        }
        return res;
    }
};

二： 只有一个元素出现一次，其他元素出现三次

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。 

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

思路： 一个数的二进制无非就是 0 或者 1， 既然除了目标数外，其他数都有三个， 那么该二进制第 i 位和 对3取余 即为 目标数的第 i 位 

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for(int i = 0; i < 32; i++) {
            int sum = 0;
            for(auto& num : nums) {
                sum += ((num >> i) & 1);
            }
            if(sum % 3) {
                res |= (1 << i);
            }
        }
        return res;
    }
};

三：两个数出现一次，其他数都出现两次 

给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

 思路： 利用异或性质，假设两个目标数为 a 和 b，那么将所有数异或后， 得到 a ^ b

因为 a 与 b 不相等， 那么a 与 b 的二进制中必然有一位不同， 即 一个为 1 ，另一个为 0，

那么我们就可以根据该位进行分组

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int xorsum = 0;
        for(int& num : nums) {
            xorsum ^= num;
        }
        int a = 0, b = 0;
        int lowbit = (xorsum == INT_MIN ? xorsum : xorsum & (-xorsum));
        for(int& num : nums) {
            if(lowbit & num) {
                a ^= num;
            }else {
                b ^= num;
            }
        }
        return {a, b};
    }
};