欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

一个数组中只有两个数字是出现一次, 其他所有数字都出现了两次。 找出这两个数字,编程实现。

程序员文章站 2024-02-02 17:05:49
...

解法一:数组遍历法

利用此方法不光能求出两个数字出现一次,更多的数字出现也可以寻找出,因为我们的本质是遍历数组,利用相同的数字就循环跳出,我们就可以找出当前不是成对出现的数字

#include<stdio.h>
#define  N 6
int main() {
	int arr[Y] = {1,2,1,2,4,5};
	int i;
	int j;
	int temp;
	for( i = 0;i<Y;i++){
		temp = arr[i];
		for(j = 0;j<Y;j++){
			//如果是相同的数字就跳出
			if((i!=j)&&(temp == arr[j])){
				break;
			}
		}
		    //如果没找到相同的数字那么判断 j == y
		    //如果相等的话说明没找到相同的数字
	        //那个数字就位不同的数字
			if(j == Y){
			printf("%d ",temp);
		}
	}
	printf("\n");
	return 0;
}

解法二:运用位运算的方法

解析 :

数组里面有一个不同的数字不断相互异或就会得到那个不同的数字(因为异或之后相同为0,0与不同的数字异或还是那个数本身)

比如

1^2 ^3 ^4 ^1 ^2 ^3

相同的数字异或后为0 那么不管怎么异或最后都会成为 0 ,剩下4与0异或

结果为4

知道这个结论之后再次解析两个不同的数字的出现:

1.首先不断异或得到的是两个数字异或后的结果
2.两个不相同数字他们的异或结果一定不为0,一定有一个位上此位有1(比如 101 110 ,异或之后为011 ,我们需要记录的是这个异或后的结果第一次出现1时候那个位!),另外一个此位上没有1,我们可以根据此位上是否有1,,将整个数组重新划分成两部分:
一部分此位上一定有1,另一部分此位上一定没有1,
4.然后分别对每部分求异或,因为划分后的两部分有这样的特点:其他数都出现两次,只有一个数只出现一次。
因此,我们又可以运用异或运算,分别得到两部分只出现一次的数。


#define  N 6
#define  Y 6
#include<stdio.h>
#include <string.h>
#include<assert.h>
void find_number(int* arr) {
	int i;
	int pos;                     //存储出现1时候的右移次数
	int number1 = 0;
	int number2 = 0;
	int temp = arr[0];
	assert(arr);
	//得到两次异或后的结果
	for(i = 1;i<N;i++) {
		temp^= arr[i];
	}
	//找出异或后先出现1 的哪一位
	for(i = 0;i<32;i++) {
		if(((temp>>i)&1)==1) {
			//将哪一位右移的次数赋值给POS
			pos = i;
			break;
		}
	}
	for( i = 0;i<N;i++) {
		//遍历数组每一个元素,将元素统一右移到那个位
		//来判断那个位上有没有1;
		if(((arr[i]>>pos)&1) == 1) {
			//那个位上有 1 的元素
			number1^=arr[i];
		}
		//那个位上没有 1 的元素,进行异或
		else number2^=arr[i];
	}
	printf("%d\n",number1);
	printf("%d\n",number2);
}
int main() {
	int arr[N] = {1,2,1,2,4,5};
	find_number (arr);
	return 0;
}
相关标签: C语言练习题