只出现一次的数字

文章目录

136. 只出现一次的数字
137. 只出现一次的数字 II
260. 只出现一次的数字 III
645. 错误的集合(拓展)

136. 只出现一次的数字

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

说明：你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

注意位异或运算的性质：

交换律：a ^ b ^ c <=> a ^ c ^ b
任何数和0 相与，为自己 0 ^ n => n
相同的数异或为0: n ^ n => 0

简单的应用：1.交换两个数字

a = a^b;  
b = b^a;  `b = a^b^b=a`
a = a^b;

//var a = [2,3,2,4,4]
//2 ^ 3 ^ 2 ^ 4 ^ 4等价于 2 ^ 2 ^ 4 ^ 4 ^ 3 => 0 ^ 0 ^3 => 3
    int singleNumber(vector<int>& nums) {
        int sign = 0;
        for(auto i:nums)
            sign ^= i;
        return sign;
    }

137. 只出现一次的数字 II

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

说明：你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

输入: [2,2,3,2]
输出: 3
---------
输入: [0,1,0,1,0,1,99]
输出: 99

我们将每一个int整数当成一个32bit的二进制组合，对于每一位的二进制的1和0累加起来必然是3N或3N+1，为3N代表目标值在这一位没贡献，3N+1代表目标值在这一位有贡献(=1)，然后将所有有贡献的位|起来就是结果。这样做的好处是如果题目改成K个一样，只需要把代码改成cnt%k，很通用,.
时间复杂度为 O(32*N)，空间复杂度为O(1)

重点: 使用一个32长度的数组统计每一位bit二进制的累加状态，然后判断每个二进制位出现的次数 bits[i] += (nums[j]>>i) & 1; int bits[32];

解法

int singleNumber(vector<int>& nums) {
        vector<int> bits(32,0);
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            for (int j = 0; j < nums.size(); j++)
                bits[i] += (nums[j]>>i) & 1;
            ans |= (bits[i] % 3) << i;
         }
      return ans;
    }

260. 只出现一次的数字 III

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。

输入: [1,2,1,3,2,5]
输出: [3,5]
# 结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
# 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

思路

有两个数只出现了一次记为 x、y，初始化为 0, 其余的数出现了两次,
我们可以对所有的数进行一次异或操作, 易知这个结果就等于 x 和 y
的异或结果 x^y (相同的数异或结果都为 0, 0和任意数异或结果都为那个数).
那么我可以考虑异或结果的某个非 0 位,如最后一个非 0 位, 因为我们知道只
有当 x、y 在该位不一样的时候才会出现异或结果为 1. 所以我们以该
位是否为 1 对数组进行划分**(这样就划分成两个数组，每个数组序列中都存在一个只出现一次的数字，既可以使用简单的异或直接找到结果)**, 只要该位为 1 就和 x 异或, 只要该位为 0就和 y 异或, 这样最终得到就是只出现过一次的两个数(其他在该位为 1 或0 的数必然出现 0/2 次对异或结果无影响)

解法

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        vector<int> res(2,0);
        int ans = 0;
        for(auto i:nums)
            ans ^= i;
        
        int bits = 1;
        // 寻找二进制表示中 最右边不为0 的位置
        // 例： ans= 0110 则bits=0010
        while((ans&1) == 0){
            ans >>= 1;
            bits <<= 1;
        }
        // 将原有的数组分为两部分，每部分中出现一个不重复元素，就可以用 异或 找到这个数字
        for(auto i:nums){
            if((i & bits) == 0 )
                res[0] ^= i;
            else
                res[1] ^= i;
        }
        return res;
    }
};

解法2

使用hash_map统计每个数字出现的次数，<数值，次数>，然后统计出现一次的数字，需要较多的空间存储状态


vector<int> singleNumber(vector<int>& nums) {
        unordered_map<int,int> numbers;
        for (int number : nums)
        {
            if (!numbers.insert(pair<int,int>(number,1)).second)
                numbers.erase(number);;//重复便移除
        }
        
        vector<int> res;
         for(auto i:numbers){
                res.push_back(i.first);
        }
        return res;
    }

645. 错误的集合(拓展)

集合 S 包含从1到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个元素复制了成了集合里面的另外一个元素的值，导致集合丢失了一个整数并且有一个元素重复。

给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

示例 1:
输入: nums = [1,2,2,4]
输出: [2,3]
# 数组无序

思路

思考一个简单的问题，一个长度为 n-1的数组包含 1 到 n 中的 n−1 个数字，有一个数字缺失，如何找出这个缺失的数字。首先使用 1 到 n 的所有数字做异或运算，然后再使用数组中的所有数字与这个数字异或，最后得到的值就是缺失数字。因为数字与其本身做异或运算结果为 0，因此所有数字做完异或后，剩余的就是缺失的数字。

{1,2,2,4} {1,2,3,4} ans = (1^1) ^ (2 ^2) ^ (2 ^3) ^ (4 ^4) = (2 ^ 3)

按照这个方法，将 nums 中所有的数字与 1 到 n 的所有数字做异或运算，得到的结果为 x^y，x和 y 分别表示 nums 中重复数字和缺失数字。
在异或结果 x^y 的二进制中，值为 1 的位置表示 x 和 y 在该位置的值不同，值为 0 的位置表示 x 和 y 在该位置的值相同。我们称 x ^y 最右边比特位为 rightmostbit，且使该位置为 1。
根据 rightmostbit不同将数组 nums 分为两部分。第一部分所有数字的 rightmostbit 为 1，第二部分所有数字的 rightmostbit 为 0。那么 x 和 y 会被分配到不同的部分。此时问题就简化为最开始的简单问题。

vector<int> findErrorNums(vector<int>& nums) {
        int ans = 0;
        int xor1=0,xor0=0;
        int len = nums.size();

        for(int i=0;i<len;i++){
            ans ^= nums[i];
            ans ^= i+1;
        }
        
        // int bits = ans & ~(ans - 1);
        int bits = 1;
        while((ans&1) == 0){
            ans >>= 1;
            bits <<= 1;
        }

        for(int n:nums){
            if ((n&bits) != 0)
                xor0 ^= n;
            else
                xor1 ^= n;
        }

        for(int i=1;i<=len;i++){
            if ((i&bits) != 0)
                xor0 ^= i;
            else
                xor1 ^= i;
        }
		// 先重复数字 再缺失数字
        for(int i:nums){
            if(xor0 == i)
                return vector<int> {xor0,xor1};
        }
        return vector<int> {xor1,xor0};
    }