什么网站可以做设计赚钱,金蝶直播,杭州公司注册地址租赁,网站开发使用什么技术1. 题目链接2. 题目描述3. 解题方法4. 代码 1. 题目链接
面试题 17.19. 消失的两个数字
2. 题目描述 3. 解题方法
例子假设#xff1a;
数组A元素为 #xff1a;1 #xff0c;4#xff0c;5
缺少的元素为#xff1a;2#xff0c; 3
那么所有整数就为1 ~ 5#xff… 1. 题目链接2. 题目描述3. 解题方法4. 代码 1. 题目链接
面试题 17.19. 消失的两个数字
2. 题目描述 3. 解题方法
例子假设
数组A元素为 1 45
缺少的元素为2 3
那么所有整数就为1 ~ 5我称这些整数为数组B
此时就有如下的图示 第1步此时将A、B两个数组的元素都异或起来所得到的结果就是2 ^ 3为了后面的讲解
我将2成为a3称为b。
第2步找到a和b异或比特位上为1的那一位
2 0 1 0
3 0 1 1
找到的这一位我在这里叫做第x位
第3步根据第x位的不同划分两类进行异或求得结果
根据上面的例子
1 0 0 1
5 1 0 1
过程 3 ^ 1 ^ 1 ^ 5 ^ 5 相同的两个数字异或直接为00异或任何数字为数字本身
这一类划分到 3 这里进行异或就得到了唯一的3
4 0 1 0
过程 2 ^ 4 ^ 4 相同的两个数字异或直接为00异或任何数字为数字本身
这一类划分到 2 这里进行异或就得到了唯一的2
4. 代码
class Solution {
public:vectorint missingTwo(vectorint nums) {// 1. 把所有相同的数都异或起来, 获得a ^ bint tmp 0;for(auto e : nums) tmp ^ e;for(int i 1; i nums.size() 2; i) tmp ^ i;// 2. 找到a ^ b 比特位为 1 的那一位int diff 0;while(1){if((tmp diff) 1 1) break;else diff ;}// 3. 划分两类数字int a 0, b 0;for(auto e : nums){if((e diff) 1 1) a ^ e;else b ^ e;}for(int i 1; i nums.size() 2; i){if((i diff) 1 1) a ^ i;else b ^ i;}return {a, b};}
};最后附上我的打卡记录希望各位大佬可以监督我。
