C语言编程题-单身狗

题号：BYTE1562

单身狗1

题目描述：一个数组中只有一个数字是出现一次，其他所有数字都出现了两次。编写一个函数找出这两个只出现一次的数字。

例如：

有数组的元素是：1，2，3，4，5，1，2，3，4

只有5只出现1次，要找出5.

#include <stdio.h>
void func1(int nums[], int len)//1.暴力解法
{
	int i = 0;
	int j = 0;
	for (i = 0; i < len; i++)
	{
		for (j = 0; j < len; j++)
		{
			if ((j != i) && (nums[i] == nums[j])) break;//如果找到除本身之外与本身相同的数就不需要再找了，跳出循环
			if (j == len - 1) printf("%d ", nums[i]);   //除本身之外的数都比较完了
		}

	}
}
void func2(int nums[], int len)//2.巧妙运用异或操作符
{
	int i = 0;
	int temp = 0;  //数组所有数异或的结果
	//因为相同的数异或的结果是0且任何数与0异或的结果是其本身，故将所有数异或，得到两个不同数异或的结果
	for (i = 0; i < len; i++)
	{
		temp ^= nums[i];
	}
	printf("%d", temp);

}

int main()
{
	int nums[] = { 1, 2, 3, 4, 5, 1, 2, 3, 4 };
	int len = sizeof(nums) / sizeof(nums[0]);
	func2(nums, len);
	return 0;
}

异或^的特性

1、两个相同的数异或的结果是0，例如5^5=0

2、任何数与0异或的结果都是它本身，例如5^0=5

3、异或满足交换律，a^b^a = a^a^b = 0^b = b

当一个数组中有一个单身狗时，由以上特性可得：a^b^c^b^a=c，可以很快得到单身的数值。

单身狗2

题目描述：一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。

编写一个函数找出这两个只出现一次的数字。

例如：

有数组的元素是：1，2，3，4，5，1，2，3，4，6

只有5和6只出现1次，要找出5和6.

#include <stdio.h>
//1.暴力解法，同上
//2.^的妙用
void func2(int nums[], int len,int *num1,int *num2)//利用指针直接将结果传出去
{
	int i = 0;
	int temp = 0;  //数组所有数异或的结果
	//因为相同的数异或的结果是0且任何数与0异或的结果是其本身，故将所有数异或，得到两个不同数异或的结果
	for (i = 0; i < len; i++)
	{
		temp ^= nums[i];
	}
	//得到两个不同的数相异的任何一位，如6(110)和4(100)异或的结果是010，第二位两个不同的数，一个数这一位是0
	//另一个就一定是1，可以由这一位将原本的数组分为两个组，其中一个组的这一位都是0，另一个组的这一位都是1
	//这样至少可以将两个不同的数分出来，其余成对的数一定在同一个组里。两个组再分别异或就可以得到两个不同的数。
	int bit = 0;//第几位异或的结果是1
	for (i = 0; i < 32; i++)
	{
		if (temp & (1 << i))//按位&的优先级没有<<高，()加不加都可以
		{
			bit = i;
			break;
		}

	}

	for (i = 0; i < len; i++)
	{
		if (nums[i] & (1 << bit))
		{
			*num1 ^= nums[i];
		}
		else
		{
            *num2 ^= nums[i];
        }
	}

}

int main()
{
	int nums[] = { 1, 2, 3, 4, 5, 1, 2, 3, 4, 6 };
	int len = sizeof(nums) / sizeof(nums[0]);
	int num1 = 0, num2 = 0;
	func2(nums, len, &num1, &num2);
	printf("%d %d", num1, num2);
	return 0;
}