L57.【LeetCode题解】位运算习题集2(只出现一次的数字 II、消失的两个数字)

原创于 2025-06-30 10:15:52 发布 · 518 阅读

21 ·

CC 4.0 BY-SA版权

文章标签：

#算法 #leetcode #哈希算法 #c++ #数据结构 #开发语言 #位运算

LeetCode题解同时被 2 个专栏收录

64 篇文章

订阅专栏

位运算

4 篇文章

订阅专栏

1.知识回顾

位运算的各种操作总结参见CC55.【C++ Cont】位运算的最终总结(含比特位计数、汉明距离)文章

2.只出现一次的数字 II

https://leetcode.cn/problems/WGki4K/description/

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

示例 1：
输入：nums = [2,2,3,2]
输出：3
示例 2：
输入：nums = [0,1,0,1,0,1,100]
输出：100
提示：

1 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
nums 中，除某个元素仅出现一次外，其余每个元素都恰出现三次

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

注意：本题与主站 137 题相同：137. 只出现一次的数字 II - 力扣（LeetCode）

方法1:哈希表

将每个元素的出现次数存入哈希表,之后遍历哈希表即可

class Solution {
public:
    int singleNumber(vector<int>& nums) 
    {
        map<int,int> mp;
        for (auto a:nums)
            mp[a]++;
        for (auto b:mp)
            if(b.second==1)
                return b.first;
        //由于一定能找到只出现一次的数字,则可以任意返回一个值
        return 0;
    }
};

提交结果:

方法2:%3看余数

以nums = [2,2,3,2]为例,改写成二进制形式:

看看每一位的特点

可以看出每一位的0和1的和只有以下几种可能:

1. 3n个0 + 1,和为3n*0+1==1

2. 3n个0 + 0,和为3n*0+0==0

3. 3n个1 + 0,和为3n*1+0==3n

4. 3n个1 + 1,和为3n*1+1==3n+1

因此只要对每一位0和1的和除以3,余数就是只出现一次的数字对应的那一位,可以自行验证

class Solution {
public:
    int singleNumber(vector<int>& nums) 
    {
        int ret=0;
        for (int i=0;i<32;i++) //int一共32位
        {
            int tmp=0;
            for (auto num:nums)
                tmp+=(num>>i)&1; //计算nums所有元素的第i位的和
            tmp%=3;
            if (tmp) //tmp==1
                ret|= 1<<i; //ret第i位修改为1
            else //tmp==0
                ret &= ~(1<<i); //ret第i位修改为0
        }
        return ret;
    }
};

运行结果:

推广

如果题改成"nums 中，除某个元素仅出现1次外,其余每个元素都恰出现n次",那么只需对每一位0和1的和除以n,余数就是只出现一次的数字对应的那一位

3.消失的两个数字(困难🌶️🌶️🌶️)

https://leetcode.cn/problems/missing-two-lcci/description/

给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？

以任意顺序返回这两个数字均可。

示例 1：
输入：[1]
输出：[2,3]
示例 2：
输入：[2,3]
输出：[1,4]
提示：

nums.length <= 30000

方法1:使用数组

如果不考虑"在 O(N) 时间内只用 O(1) 的空间"这个要求,比较好想

将缺了两个数字的从 1 到 N 所有的整数按arr[i]=i的规则存储大小为N+1的数组中,之后遍历该数组,

如果发现arr[i]!=i就将结果尾插到要返回的vector<int> ret中

时间复杂度 $O(N)$ ,空间复杂度 $O(N)$

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) 
    {
        int* arr=new int[nums.size()+3];
        vector<int> ret;
        memset(arr,0,(nums.size()+1)*sizeof(int));
        for (auto& num:nums) 
            arr[num]=num;
        for (int i=1;i<nums.size()+3;i++)
        {
            if (arr[i]!=i)
                ret.push_back(i);
            if (ret.size()==2)
                break;
        }       
        return ret;
    }
};

提交结果:

方法2:位运算★

需要用到L56.【LeetCode题解】位运算习题集1(只出现一次的数字 III、判定字符是否唯一、两整数之和)的只出现一次的数字 III和E27.【C语言】练习：在一个整型数组中，只有一个数字出现一次，其他数组都是成对出现的，请找出那个只出现一次的数字的算法思想

对缺了两个数字从 1 到 N 所有的整数加上完整的从1到N的所有数就转化成了只出现一次的数字 III题(恰好有两个元素只出现一次，其余所有元素均出现两次)

版本1

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) 
    {
        unsigned int res=0;
        for (auto a:nums)
            res^=a;
        unsigned int classify_num=res & (-res);  
        unsigned int group1=0,group2=0;
        for (auto a:nums)  
        {
            if (a&classify_num)
                group1^=a;
            else
                group2^=a;
        }
        vector<int> ret;
        ret.push_back(group1);
        ret.push_back(group2);
        return ret;
    }

    vector<int> missingTwo(vector<int>& nums) 
    {
        int ori_size=nums.size();
        for (int i=1;i<ori_size+3;i++)
            nums.push_back(i);
        vector<int> ret=singleNumber(nums);
        return ret;
    }
};

时间复杂度 $O(N)$ ,空间复杂度 $O(N)$

版本2

其实不用尾插1~N个完整的数字,稍微改下只出现一次的数字 III的代码就行了

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) 
    {
        unsigned int res=0;

        for (auto a:nums)
            res^=a;
        for (int i=1;i<nums.size()+3;i++)//等价为尾插1~N个完整的数字
            res^=i;

        unsigned int classify_num=res & (-res);  
        unsigned int group1=0,group2=0;

        for (auto a:nums)  
        {
            if (a&classify_num)
                group1^=a;
            else
                group2^=a;
        }
        for (int i=1;i<nums.size()+3;i++)//等价为尾插1~N个完整的数字
        {
            if (i&classify_num)
                group1^=i;
            else
                group2^=i;
        }

        vector<int> ret;
        ret.push_back(group1);
        ret.push_back(group2);
        return ret;
    }
};

时间复杂度 $O(N)$ ,空间复杂度 $O(1)$