【C国演义】第一章

一堆数字里面，有且仅有一个数字出现的次数是奇数次，其他的数字出现的次数全为偶数次，求出这个数字（要求时间复杂度O（N））

• 分析：
  要求时间复杂度是O（ N ），那我们想暴力解决的想法就落空了。那我们可以另辟蹊径：
  其他数字出现的次数全为偶数次 ： 那么异或 （ ^ ）的结果就是 0 喽。那么在异或一次，那么结果是另一个数了。

• 普及知识：（ ^ ）

1. 我们可以把异或看做是二进制的无进位相加
   
2. 异或的性质：
   ① a ^ 0 = a;
   ②a ^ a = 0;
   ③满足交换律和结合律
   ④ 一堆数字跟一个数字异或 ——> 可以有选择地进行异或
   性质 3 和 4 的原因：
   无进位相加 ——主要看的是二进制位中 1 的个数，那就不看重计算的顺序喽

#include

int main()
{
	int ret = 0, n; //ret用来记录异或结束的结果（即答案）
	scanf("%d", &n);
	while (n--)
	{
		int a;  scanf("%d", &a);
		ret ^= a;
	}

	printf("%dn", ret);

	return 0;
}

🐉🐉🐉🐉🐉我在这里说一声吧：（以免有些人想不到，比如当时的我）
起初， ret = 0，其实是有门道的：因为它是用来记录异或结束的结果，所以用 0 来初始化，因为 0 异或任意一个数都等于这个数本身

你以为这个题会了吗，那咋们来进入下一题（也是有关异或的）

给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。要求时间复杂度是O（1）

提示：
2 -2^31 除两个只出现一次的整数外，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

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;
}

最近由于一些事情，耽误了更新博客，很长时间，没写博客，手生，界面外貌不好看，请大家见谅。但我本人保证，内容肯定还是充足的。

更新不易，请大家三连走一波！！！

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net