C语言编程题-单身狗

发布时间:2023年12月20日

题号: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;
}
文章来源:https://blog.csdn.net/qq_52907930/article/details/134980111
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。