本文共 3402 字，大约阅读时间需要 11 分钟。

（1）有101个整数，其中有50个数出现了两次，1个数出现了一次， 找出出现了一次的那个数。

#include 
   
    #define MAX 20int case1(int arr[], int length);               void case2(int arr[], int length, int res[]);void case3(int arr[], int length, int res[]);int main(){
   	int arr1[] = {
    1,2,2,3,3,4,4,5,5,6,6 };	int res1;	res1 = case1(arr1, sizeof(arr1) / sizeof(int));	int arr2[] = {
    1,2,3,3,4,4,5,5,6,6,7,7 };	int res2[2];	case2(arr2, sizeof(arr2) / sizeof(int), res2);	int arr3[] = {
    2,4,6,9,9,5,5,10,10,7,7,8,8 };	int res3[3];	case3(arr3, sizeof(arr3) / sizeof(int), res3);	return 0;}int case1(int arr[], int length){
   	int xorRes = 0;	for (int i = 0; i < length; ++i)	{
   		xorRes ^= arr[i];   //采用异或运算，异或运算满足交换律，并且一个数和自身异或为0，和0异或为其本身		}	return xorRes;}void case2(int arr[], int length, int res[]){
   	int xorRes = case1(arr, length);	int divider = xorRes & -xorRes;  //找到两个不相等的数一个bit为1的位置(最高位)	int heap1[MAX] = {
    0 };	int length1 = 0;                //将这个数组分成两堆数据，这两堆数据中分别包含互不相等的数字	int heap2[MAX] = {
    0 };	int length2 = 0;	for (int i = 0; i < length; ++i)	{
   		if (arr[i] & divider)      //如果arr[i]和divider&结果为1，说明arr[i]的那个bit位也为1		{
   			heap1[length1++] = arr[i];			//0，1，2，。。。length1-1		}		else                      //如果arr[i]和divider&结果为1，说明arr[i]的那个bit位为0		{
   			heap2[length2++] = arr[i];		}	}	res[0] = case1(heap1, length1);	res[1] = case1(heap2, length2);}void case3(int arr[], int length, int res[]){
    	int divider = 1;               // 测试divider能否成功分堆，不能的话 divider <<= 1	int heap1[MAX] = {
    0 };	int length1 = 0;	int heap2[MAX] = {
    0 };	int length2 = 0;	for (int pos = 1; pos < sizeof(int) * 8; ++pos, divider <<= 1)     //共32位bit，遍历32位的每一个bit为1时，能否将数据成功分成两堆	{
   		length1 = 0;		length2 = 0;		for (int i = 0; i < length; ++i)       //采用case2中的方法尝试分堆		{
   			if (arr[i] & divider)			{
   				heap1[length1++] = arr[i];						}			else			{
   				heap2[length2++] = arr[i];			}		}		if (length1*length2)                  //如果length1和length2都不为0，尝试将数据分成两堆		{
   			int xorRes1 = case1(heap1, length1);   			int xorRes2 = case1(heap2, length2);			if (xorRes1 * xorRes2)            //如果xorRes1和xorRes2的都不为0，说明分堆成功，一堆含有1个数字，一堆含2个数字			{
   				if (length1 % 2 == 0)         //第一堆为偶2个，第二堆则为1个				{
   					res[0] = xorRes2;         //将第二堆数据的异或结果赋值给res[0]					case2(heap1, length1, res + 1);       //再调用case2()函数解决heap1，需要传入res+1即res[1]的地址				}				else				{
   					res[0] = xorRes1;					case2(heap2, length2, res + 1);				}				break;              //成功解决问题			}			else			{
   				continue;			}		}		else		{
   			continue;		}	}}
   

另一种通用解法可以讲数组中的元素导入到结构体，向结构体中添加一个计数器就可以解决问题。

#include
   
    #include
    
     using namespace std;struct MyArray {
   	int data;	int count = 0;     //对data出现的次数进行计数};int main() {
   	MyArray array[100];	int p = 0;	for (int i = 0; i < 10; i++) {
               //此处只测试10个数据		int flag = 1;      //标记位		int num;		cin >> num;		for (int j = 0; j < p; j++) {
           //对当前输入数字之前的数字进行遍历			if (array[j].data == num) {
           //如果发现存在和当前数字相等的数字，将标志位置为0				array[j].count++;          				flag = 0;				break;			}		}		if (flag == 1) {
               //说明当前输入的数字在array中未出现过			array[p].data = num;			array[p].count = 1;			p++;                  //array中不同数字的数量		}	}	for (int i = 0; i < p; i++) {
   		if (array[i].count == 1) {
   			cout << array[i].data << endl;		}	}	return 0;}
    
   

转载地址：http://rtxmb.baihongyu.com/