面试题--消失的两个数字(困难)

发布时间:2024年01月06日

?个人主页:Lei宝啊?

愿所有美好如期而遇?


目录

本题链接

输入描述

输出描述

算法分析

触类旁通一:消失的数字

题目分析

图示

解题源码

触类旁通二:只出现一次的数字III

题目分析

图示

解题源码

本题分析

解题源码?


本题链接

力扣(LeetCode)

输入描述

输入一个数组,但是这个数组实际上缺失了两个元素,并且元素最小为1。

我们输入1,也就是说,这个数组最大的元素max为nums.size() + 2,从1到max缺失了两个数。

输出描述

输出缺失的两个数。

算法分析

本题我们可以参考消失的数字,以及只出现一次的数字III,结合这两道题目,其实就已经可以尝试做这道题了,我们先来看消失的数字这道题目。

触类旁通一:消失的数字

题目分析

给定一个数组,数组元素的最大值max为nums.size(),但是这个数组缺失了一个数字,所以数组长度为nums.size()+1,我们要找缺失的那一个数字,就先定义一个变量ret = 0,让他异或这个数组,之后再遍历异或从下标0到下标nums.size()的自然数数组,就是我们缺失的数字

图示

解题源码
class Solution {
public:
    int missingNumber(vector<int>& nums) 
    {
        int n = nums.size() + 1;
        int ret = 0;

        for(int i=0; i<n; i++) ret ^= i;
        for(int i=0; i<n-1; i++) ret ^= nums[i];

        return ret;
    }
};
触类旁通二:只出现一次的数字III

题目分析

给定一个数组,整个数组中只有两个数出现一次,其他数字都出现两次,我们创建变量ret = 0异或这个数组,最后ret实际上是这两个数的异或,我们如何将ret拆分出来这两个数呢?

首先,这两个数是不同的,也就是说他们32位比特位,至少有一位是不同的,我们找到这个不相同的比特位作为这两个数的区分,位置标记为pos,然后定义一个变量num = 0,在nums整个数组中,找到pos位置比特位为1的数字进行异或,由于其他数字都是成对的,所以最后剩下来的就是两个数中的一个,我们再用ret异或得到另一个

图示

解题源码
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) 
    {
        int ret = 0, pos = 0, n = nums.size();
        for(int i=0; i<n; i++) ret ^= nums[i];
        for(int i=0; i<32; i++) 
        {
            if(((ret >> i) & 1) == 1)
            {
                pos = i;
                break;
            }
        }

        int num = 0;
        for(int i=0; i<n; i++)
        {
            if(((nums[i] >> pos) & 1) == 1) 
                num ^= nums[i];      
        }

        return vector<int>{num,num^ret};
    }
};
本题分析

有了上面两道题的分析,这道题我们也就是结合了缺失数字,并且缺失了两个数字。

首先缺失两个数字,我们需要异或,异或本数组,再异或一个自然数组,得到的就是这两个缺失数的异或,接着就是分开这两个数了,不就是找两个数不同的比特位pos位置,然后在nums数组和自然数组里挑选pos位置为1的数进行异或,最后区分开?

解题源码?

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) 
    {
        int max = nums.size() + 2;
        int ret = 0, pos = 0, div = 0;

        for(auto num : nums) ret ^= num;
        for(int i=1; i<=max; i++) ret ^= i;
        for(int i=0; i<32; i++) 
        {
            if((1 & (ret >> i)) == 1) 
            {
                pos = i;
                break;
            }
        }
        
        for(int i=0; i<nums.size(); i++) 
        {
            if(((nums[i] >> pos) & 1) == 1)
            div ^= nums[i];
        }

        for(int i=1; i<=max; i++)
        {
            if(((i >> pos) & 1) == 1)
            div ^= i;
        }
        
        return vector<int>{div,ret^div};
    }
};

文章来源:https://blog.csdn.net/m0_74824254/article/details/135423780
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。