算法日常・每日刷题--＜位运算＞5

面试题 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]数组长度为 1 →N = 1 + 2 = 3，完整序列[1,2,3]，缺失[2,3]，输出[2,3]
2. 输入：[2,3]数组长度为 2 →N = 2 + 2 = 4，完整序列[1,2,3,4]，缺失[1,4]，输出[1,4]

用异或运算

异或基础性质

1. 交换律、结合律：a ^ b ^ c = a ^ c ^ b；
2. 相同数字异或抵消：x ^ x = 0；
3. 任何数异或 0 不变：x ^ 0 = x；
4. 异或区分二进制位：a ^ b的二进制中，为 1 的位代表 a、b 该位数值不同。

1.用异或运算找出两个没有出现的数字

2.用异或运算将两个数分在两组

用什么方法对其进行分组,由于这两个数是不一样的,必然会有一位是1一位是0

将那一位是1还是0,对所有的数进行分类,再将数进行按组进行异或操作,即可得到答案

class Solution { public: vector<int> missingTwo(vector<int>& nums) { //将所有数字异或在一起得到没有出现的两个数异或在一起的结果 int ret=0; for(auto e:nums) ret=ret^e; for(int i=1;i<=nums.size()+2;i++) ret=ret^i; //找到某一位唯一的位置 int diff=0; while(diff<32) { if(((ret>>diff)&1)==1) break; else diff++; } int a=0,b=0; for(auto e:nums) { if( ((e>>diff) & 1) == 1 ) { a=a^e; } else { b=b^e; } } for(int i=1;i<=nums.size()+2;i++) { if( ((i>>diff) & 1) == 1 ) { a=a^i; } else { b=b^i; } } return {a,b}; } };