找到数组中消失的两个数字

本是古典何须时尚 2022-11-03 15:30 156阅读 0赞

一道位运算题目，和其他几道题目有相似的地方，都是异或的使用

[题目链接][Link 1]

这里提供三种好理解的思路

**思路1：**

因为这里数组是递增的，可以求和，否则不行

*  1 + … + (N+2) 肯定是最终和
 *  把已知所有数字加起来和期望和比较，可得a+b
 *  因为这里数组是递增的，从左往右开始寻找第一个下标不正确的数字，即a
 *  这样就可以求得a和b

**思路1 - 题解：**

class Solution {
        
    public:
        vector<int> missingTwo(vector<int>& nums) {
        
            if(nums.size() <= 0) return {
        };
            sort(nums.begin(), nums.end());
            long total = (nums.size() + 2) * (1 + nums.size() + 2) / 2;
            int a = -1;
            for(int i=1; i<=nums.size(); i++){
        
                if(nums[i-1] != i){
        
                    a = i;  // 找到第一个缺少的数字
                    break;
                }
            }
            if(a == -1) a = nums.size() + 1;
            for(auto number : nums){
        
                total -= number;
            }
            return {
        a, (int)total - a};
        }
    };

--------------------

**思路2：**

使用二次根式

(a+b)2 = a2 \+ 2ab + b2  
(a -b)2 = a2 \- 2ab + b2

*  容易求得1 + … + (N+2)，因此可以得到a + b = x
 *  容易求得12 \+ 22 \+ … + (N+2)2 ，因此可以得到a2 \+ b2 = y
 *  因此可以求得 ab = (x2 \- y) / 2
 *  已经知道 a + b 和 ab ，就可以求得 a - b
 *  已知 a + b 和 a - b ，可以最终求得 a 与 b

**思路2 - 题解：**

class Solution {
        
    public:
        vector<int> missingTwo(vector<int>& nums) {
        
            if(nums.size() <= 0) return {
        };
            long total = (nums.size() + 2) * (1 + nums.size() + 2) / 2; // a + b 
            long total2 = 0;    // a^2 + b^2
            for(int i=1; i<=nums.size()+2; i++){
        
                total2 += i * i;
            }
            for(auto number : nums){
        
                total -= number;
                total2 -= number * number;
            }
            long total3 = (total * total - total2) / 2; // a * b
            long total4 = sqrt(total2 - total3 * 2);    // a - b
            int a = (long)(total + total4) / 2;
            int b = (int)total - a;
    
            return {
        a, b};
        }
    };

--------------------

**思路3：**

使用异或：a ^ a = 0

*  已知的所有数字的异或结果为 a ^ b
 *  因为 a 和 b 一定不相同，因此 a 与 b 的异或结果一定不为0，因此，一定有一位为1
 *  找到任意一位1，使用这个数字作为判断依据mask，a 和 b 对于这个数字的异或结果一定不相同
 *  设初始 a 和 b 均为0，异或所有已知数字和范围内所有数字，根据mask判断与a异或还是与b异或，这样分成两组
 *  最终的计算结果就是a 和 b 的值

**思路3 - 题解：**

class Solution {
        
    public:
        vector<int> missingTwo(vector<int>& nums) {
        
            if(nums.size() <= 0) return {
        1,2};
            int temp = 0;   // temp 为 a ^ b结果
            int a = 0, b = 0;
            for(int i=1; i<=nums.size()+2; i++){
        
                temp ^= i;
            }
            for(int i=0; i<nums.size(); i++){
        
                temp ^= nums[i];
            }
            // 找到mask数值
            int mask = temp & (-temp);
            for(int i=1; i<=nums.size()+2; i++){
        
                if(mask & i){
        
                    a ^= i;
                }else{
        
                    b ^= i;
                }
            }
            for(int i=0; i<nums.size(); i++){
        
                if(mask & nums[i]){
        
                    a ^= nums[i];
                }else{
        
                    b ^= nums[i];
                }
            }
            return {
        a, b};
        }
    };

[Link 1]: https://leetcode-cn.com/problems/missing-two-lcci/