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

93 阅读 0 评论 62 点赞

我是靠谱客的博主落后黑裤，最近开发中收集的这篇文章主要介绍一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。编写一个函数找出这两个只出现一次的数字。二：一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。编写一个函数找出这两个只出现一次的数字。，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一：（这只有一个不同数字，相对简单点）（两个的在最后）一个数组中只有一个数字是出现一次，其他所有数字都出现了两次。编写一个函数找出这一个只出现一次的数字。

1.暴力法：一个个对比，有相等的则去掉

2.一维数组法：此法有局限性，如果数组中有过于大的数字则不适用

3.二维数组法:

4.二进制异或：相同的数字进行异或会抵消掉，所以只需用0与数组内所有元素进行异或，就可找出单独的数字

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

1.二进制异或

一：（这只有一个不同数字，相对简单点）（两个的在最后）一个数组中只有一个数字是出现一次，其他所有数字都出现了两次。编写一个函数找出这一个只出现一次的数字。

1.暴力法：一个个对比，有相等的则去掉

#include<stdio.h>

int Findnum(int ar[], int n)
{
	int i, j;
	for (i = 0; i < n; ++i)
	{
		for (j = 0; j < n; ++j)
		{
			if (i == j)
				continue;
			if (ar[i] == ar[j])
				break;
		}
		if (j == n)
			break;
	}
	return ar[i];
}

void main()
{
	int ar[5] = { 1, 2, 3, 3, 1 };
	int n = sizeof(ar) / sizeof(ar[0]);
	int res = Findnum(ar, n);
	printf("res = %dn", res);
}

2.一维数组法：此法有局限性，如果数组中有过于大的数字则不适用

#include<stdio.h>

int Findnum(int ar[], int n)
{
	int tem[100] = { 0 };
	for (int i = 0; i < n; i++)
	{
		tem[ar[i]]++;
	}
	for (int i = 0; i < n; ++i)
	{
		if (tem[i] == 1)
			return i;
	}
}

void main()
{
	int ar[5] = { 1, 2, 3, 3, 1 };
	int n = sizeof(ar) / sizeof(ar[0]);
	int res = Findnum(ar, n);
	printf("res = %dn", res);
}

3.二维数组法:

#include<stdlib.h>
#include<assert.h>

int Findnum(int ar[], int n)
{
	int **tem = (int **)malloc(n* sizeof(int *));
	assert(tem != NULL);
	for (int i = 0; i < n; ++i)
	{
		tem[i] = (int *)calloc(2, sizeof(int));
	}

	int k = 0;
	for (int i = 0; i < n; ++i)
	{
		int j;
		for ( j = 0; j < k; j++)
		{
			if (ar[i] == tem[j][0])
				tem[j][1]++;
		}
		if (j >= k)
		{
			tem[k][0] = ar[i];
			tem[k][1] = 1;
			k++;
		}
	}
	int res = 0;
	for (int i = 0; i < ((n + 1) / 2); ++i)
	{
		if (tem[i][1] == 1)
			res = tem[i][0];
	}
	return res;

	for (int i = 0; i < n; ++i)
	{
		free(tem[i]);
	}
	free(tem);

}


void main()
{
	int ar[5] = { 1, 2, 3, 3, 1 };
	int n = sizeof(ar) / sizeof(ar[0]);
	int res = Findnum(ar, n);
	printf("res = %dn", res);
}

4.二进制异或：相同的数字进行异或会抵消掉，所以只需用0与数组内所有元素进行异或，就可找出单独的数字

int Findnum(int ar[], int n)
{
	int res = 0;
	for (int i = 0; i < n; ++i)
	{
		res ^= ar[i];
	}
	return res;
}

void main()
{
	int ar[5] = { 1, 2, 3, 3, 1 };
	int n = sizeof(ar) / sizeof(ar[0]);
	int res = Findnum(ar, n);
	printf("res = %dn", res);
}

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

1.二进制异或

异或的特点就是两个相同的数字进行异或，得到的结果为0，比如：6 ^ 6 = 0；

利用这个特点，先将数组内所有数字进行异或就得到了，两个只出现一次的数字，

5和6的异或结果为3

然后找到其结果任意二进制为1(异或结果不同才会为1)的一位赋值给mask

用mask来将数组内所有数字分为两类：5 和 6 肯定不会在同一个组

然后将所得到的两个组分别进行异或，此时就得到了两个只出现一次的数字5 和6；

int* FindData(int ar[], int n)
{
	int tmp = 0;
	for (int i = 0; i<n; ++i)
		tmp ^= ar[i];
	//0000 0101  5
	//0000 0110  6
	//0000 0011  3
	int mask = 0x01;
	//0000 0001
	//0000 0011  tmp
	//0000 0001  mask & tmp第一次!=0 跳出循环

	while ((mask & tmp) == 0)
		mask <<= 1;

	int *res = (int*)calloc(2, sizeof(int));
	assert(res != NULL);

	//mask = 0000 0001 用mask将数组分为两部分
	//res = 0;

	for (int i = 0; i<n; ++i)
	{
		if ((ar[i] & mask) != 0)
			res[0] ^= ar[i];//res[0] = 0 ^ 1^ 5^ 1 = 5
		else
			res[1] ^= ar[i];//res[1] = 0 ^ 6 ^4 ^4 = 6
	}

	return res;//返回5和6
}

void main()
{
	//0000 0101  5
	//0000 0110  6
	//0000 0011  3

	int ar[] = { 1, 5, 1, 4, 6, 4};
	int n = sizeof(ar) / sizeof(ar[0]);

	int sz = 2;
	int *res = FindData(ar, n);
	for (int i = 0; i<sz; ++i)
		printf("%d ", res[i]);
	printf("n");
}