面试题 17.19. 消失的两个数字 - 力扣LeetCode面试题 17.19. 消失的两个数字 - 给定一个数组包含从 1 到 N 所有的整数但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗以任意顺序返回这两个数字均可。示例 1输入[1]输出[2,3]示例 2输入[2,3]输出[1,4]提示 * nums.length 30000https://leetcode.cn/problems/missing-two-lcci/description/一、题目简介题目描述给定一个数组nums原本完整序列是连续整数1,2,3,...,N现在数组中恰好缺失两个不同数字数组长度len N - 2。 要求在O(N)时间复杂度、O(1)常数额外空间内找出这两个消失的数字返回顺序不限。示例输入[1]数组长度为 1 →N 1 2 3完整序列[1,2,3]缺失[2,3]输出[2,3]输入[2,3]数组长度为 2 →N 2 2 4完整序列[1,2,3,4]缺失[1,4]输出[1,4]用异或运算异或基础性质交换律、结合律a ^ b ^ c a ^ c ^ b相同数字异或抵消x ^ x 0任何数异或 0 不变x ^ 0 x异或区分二进制位a ^ b的二进制中为 1 的位代表 a、b 该位数值不同。1.用异或运算找出两个没有出现的数字2.用异或运算将两个数分在两组用什么方法对其进行分组,由于这两个数是不一样的,必然会有一位是1一位是0将那一位是1还是0,对所有的数进行分类,再将数进行按组进行异或操作,即可得到答案class Solution { public: vectorint missingTwo(vectorint nums) { //将所有数字异或在一起得到没有出现的两个数异或在一起的结果 int ret0; for(auto e:nums) retret^e; for(int i1;inums.size()2;i) retret^i; //找到某一位唯一的位置 int diff0; while(diff32) { if(((retdiff)1)1) break; else diff; } int a0,b0; for(auto e:nums) { if( ((ediff) 1) 1 ) { aa^e; } else { bb^e; } } for(int i1;inums.size()2;i) { if( ((idiff) 1) 1 ) { aa^i; } else { bb^i; } } return {a,b}; } };