【位运算】leetcode面试题：消失的两个数字

一.题目描述

消失的两个数字

二.思路分析

本题难度标签是困难，但实际上有了只出现一次的数字iii这道题的铺垫，本题的思路还是很容易想到的。

温馨提示：阅读本文前可以先查看我的【位运算】专栏的第一篇文章，其中包含位运算这类题型的常用技巧以及前面这道题的讲解。

言归正传，这道题最容易想到的解法应该是哈希表，遍历数组，用哈希表记录每个元素出现的次数。然后再遍历哈希表，出现次数为0的元素就是我们要找的答案。但是空间复杂度为O(n)，不符合题目要求。

下面介绍位运算的方法：

若数组的长度为n，则数组缺少了[1, n+2]中的两个数。

先将从1到n+2的所有整数异或在一起，然后再异或数组的每个元素。异或的特点是“消消乐”，即两个相同的数异或会变成0，故最终的结果tmp相当于这两个缺失的数异或。

这两个数既然不同，那么它们至少有一个比特位不一样，我们可以遍历tmp的每一个比特位，如果它是1，则说明两个数的这一位不相同（异或的规则是相异为1），记录这一位置。

随后我们根据这一比特位的不同，将[1,n+2]的整数以及数组的所有元素划分为两组，分别进行异或，相同的元素会消去，最终得到的就是我们要找的两个数。

三.代码实现

class Solution {
public:vector<int> missingTwo(vector<int>& nums) {int n = nums.size();int tmp = 0;//将所有数异或在一起for (int i = 1; i <= n + 2; i++){tmp ^= i;}for (auto e : nums){tmp ^= e;}//找出缺失的两个数字哪一比特位不相同int pos = 0;for (int i = 0; i <= 31; i++){if (((tmp >> i) & 1) == 1){pos = i;break;}}//根据这一比特位不同,划分为两组分别异或int ret1 = 0, ret2 = 0;for (int i = 1; i <= n + 2; i++){if (((i >> pos) & 1) == 1){ret1 ^= i;}else{ret2 ^= i;}}for (auto e : nums){if (((e >> pos) & 1) == 1){ret1 ^= e;}else{ret2 ^= e;}}return {ret1, ret2};}
};

欢迎进入我的主页，翻阅算法专栏，学习更多有趣的算法。