刷题集 - 初入 - 异或
一堆数字里面，有且仅有一个数字出现的次数是奇数次，其他的数字出现的次数全为偶数次，求出这个数字（要求时间复杂度O（N））
分析：
要求时间复杂度是O（ N ），那我们想暴力解决的想法就落空了。那我们可以另辟蹊径：
其他数字出现的次数全为偶数次 ： 那么异或 （ ^ ）的结果就是 0 喽。那么在异或一次，那么结果是另一个数了。
普及知识：（ ^ ）
1.我们可以把异或看做是二进制的无进位相加
2.异或的性质：
① a ^ 0 = a;
②a ^ a = 0;
③满足交换律和结合律
④ 一堆数字跟一个数字异或 ——> 可以有选择地进行异或
性质 3 和 4 的原因：
无进位相加 ——主要看的是二进制位中 1 的个数，那就不看重计算的顺序喽
#include<stdio.h> int main() { int ret = 0, n; //ret用来记录异或结束的结果（即答案） scanf("%d", &n); while (n--) { int a; scanf("%d", &a); ret ^= a; } printf("%d\n", ret); return 0; }
🐉🐉🐉🐉🐉我在这里说一声吧：（以免有些人想不到，比如当时的我）
起初， ret = 0，其实是有门道的：因为它是用来记录异或结束的结果，所以用 0 来初始化，因为 0 异或任意一个数都等于这个数本身
你以为这个题会了吗，那咋们来进入下一题（也是有关异或的）
给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。要求时间复杂度是O（1）
提示：
2 <= nums.length <= 3 * 104
-2^31 <= nums[i] <= 2 ^31 - 1
除两个只出现一次的整数外，nums 中的其他数字都出现两次
看到这里，有些同学就兴奋了：这不就是刚才写的题吗？送分题！！
确实，跟刚才写的题很相。但是，我们要理清题目之间的内在联系：
如果按照刚才的思路，全部异或，那么结果就是那两个只出现一次的元素的异或结果。
那我们接下来的任务就是：区分开这两个数。
那么问题来了，怎么区分开这两个数，换句话说：这两个有什么不同。
🐉🐉🐉
思路：
1.通过前面的知识可以知道：这两个数异或的结果（暂时记为 eor ）必然不等于 0 。因为：这两个数出现的次数都是奇数次，那么肯定至少有一个二进制位不同，那么这个位置异或的结果就是 1 。
2.那我们可以找到 eor 最右边的一个 1 ，以此作为分组的依据，将 nums 数组分成两部分。
3.两个部分分批进行异或，得到的两个异或结果就是这两个只出现一次的元素。
（在这里，我们还有一种思路：将 eor 最右边是 1 的那一部分进行异或得到的是一个结果（记作 a ）， 那么用 eor ^ a ,得到的就是另一个结果（记作 b）），原因就是：异或操作可以进行交换律和结合律：eor ^ a == (a ^ b ) ^ a == (a ^ a ) ^ b == 0 ^ b == b
有人又要问了：嗯？？为什么这样可以取出 eor 最右边的 1 ？？ 原理是什么？？
#include<stdio.h> int main() { int nums[100]; int n; scanf("%d", &n); int res = 0; for (int i = 0; i < n; i++) { scanf("%d", &nums[i]); res ^= nums[i]; } int tem = 0; int rightone = res & (~res + 1); for (int i = 0; i < n; i++) { if ((nums[i] & rightone) == 0) //res最右边位置是 1 的那一组 tem ^= nums[i]; } printf("%d %d", tem, res ^ tem); return 0; }
