海宁长安网站开发,建设厅工作证查询网站,做视频网站需要什么软件有哪些,wordpress 底部模板一.题目描述
消失的两个数字 二.思路分析
本题难度标签是困难#xff0c;但实际上有了只出现一次的数字iii这道题的铺垫#xff0c;本题的思路还是很容易想到的。
温馨提示#xff1a;阅读本文前可以先查看我的【位运算】专栏的第一篇文章#xff0c;其中包含位运算这类…一.题目描述
消失的两个数字 二.思路分析
本题难度标签是困难但实际上有了只出现一次的数字iii这道题的铺垫本题的思路还是很容易想到的。
温馨提示阅读本文前可以先查看我的【位运算】专栏的第一篇文章其中包含位运算这类题型的常用技巧以及前面这道题的讲解。
言归正传这道题最容易想到的解法应该是哈希表遍历数组用哈希表记录每个元素出现的次数。然后再遍历哈希表出现次数为0的元素就是我们要找的答案。但是空间复杂度为O(n)不符合题目要求。
下面介绍位运算的方法 若数组的长度为n则数组缺少了[1, n2]中的两个数。 先将从1到n2的所有整数异或在一起然后再异或数组的每个元素。异或的特点是“消消乐”即两个相同的数异或会变成0故最终的结果tmp相当于这两个缺失的数异或。 这两个数既然不同那么它们至少有一个比特位不一样我们可以遍历tmp的每一个比特位如果它是1则说明两个数的这一位不相同异或的规则是相异为1记录这一位置。 随后我们根据这一比特位的不同将[1,n2]的整数以及数组的所有元素划分为两组分别进行异或相同的元素会消去最终得到的就是我们要找的两个数。 三.代码实现
class Solution {
public:vectorint missingTwo(vectorint 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};}
};
欢迎进入我的主页翻阅算法专栏学习更多有趣的算法。
