目录

一.问题描述

二. 方法一：排序法

题解代码： 

三.方法二：位运算法

第一步：

第二步：

第三步：

题解代码：

方法三：顺序表记录法

第一步：

第二步：

第三步：

第四步：

题解代码：

一.问题描述

数组arr中只有两个数字是出现一次，其他所有数字都出现了两次。

编写一个函数找出这两个只出现一次的数字。(数组元素个数假设为sz)函数返回一个两个元素的数组的首地址(数组在堆区上创建，该数组中存放数组arr中两个只出现了一次的数字)。

示例：

给定数组{4,2,3,6,7,8,9,10,12,5,2,3,6,7,11,9,10,12,4,5 }; 

函数返回的数组(首地址)：[8,11];

题解接口定义:int* FindNum1(int* arr, int sz);

(函数返回一个存储查找结果的数组)

(sz为数组的大小)

二. 方法一：排序法

注意数组排好序后，当待查找的元素位于数组边界位置时的情况需要单独拎出来判断处理。

题解代码： 

//方法一：排序
int cmp(const void* e1, const void* e2)
{return *(int*)e1 - *(int*)e2;
}
int* FindNum1(int* arr, int sz)
{assert(arr);int* ptr = (int*)malloc(2 * sizeof(int)); //为存放查找结果的数组申请堆区上的空间if (ptr == NULL)                          //判断指针的有效性{perror("malloc failed\n");return NULL;} qsort(arr, sz, sizeof(int), cmp);         //用快排对数组进行排序int count = 0;                            //count用来记录找到了几个元素     if (arr[0] - arr[1])                      //先进行左边界判断{ptr[count++] = arr[0];}else if (arr[sz - 1] - arr[sz - 2])       //再进行后边界判断{ ptr[count++] = arr[sz - 1];}if (count == 2){return ptr;}int i = 0;                                //判断除边界外的元素是否满足情况for (i = 1; i < sz-1; i++){if (arr[i]-arr[i - 1] && arr[i]-arr[i + 1]){ptr[count++] = arr[i];if (count == 2){return ptr;}}}return ptr;
}

该方法的时间复杂度就是排序的时间复杂度：O(nlogn).

三.方法二：位运算法

数组元素的异或和：将数组所有元素进行异或运算得到的结果.

比如一个数组:[1,2,3,4],则该数组的异或和为：1^2^3^4.

注意异或运算满足交换律和结合律

第一步：

求数组arr的异或和NorSum：

	int i = 0;int NorSum = 0;                         //0异或x(x为任意值)结果为x，NorSum一定要初始化为0for (i = 0; i < sz; i++){NorSum ^= arr[i];                   //NorSum=x^y ,NorSum记录了x和y的不同位}

第二步：

记录NorSum的某一位1,把该为1记录于lowbit中，用于将数组的元素进行分组

该步骤有两种方法：

方法1：lowbit= NorSum&(-NorSum)

方法原理：假设x为正数，将x符号位变为1，其余位按位取反，这时得到-x的反码，-x的反码与x的每一位都不一样，这时-x的反码再加上1(这时会得到-x的补码)，其最低位的0就会变为1，而-x的反码的最低位的0对应x最低位的1，所以 -x&x的结果就记录了x的最低位的1。

方法2：利用循环逐位去找NorSum的某一位1并记录其位置：

for (i = 0; i < 32; i++){if (NorSum & (1 << i)){lowbit= (1<

lowbit记录了NorSum最低位的1的位置。

我们采用方法1

第三步：

利用lowbit以按位与的方式对数组元素进行分组

	int Lowbit = NorSum &(-NorSum);          /*取出NorSum中的最低位，该最低位可以将arr中的数 分为两组*/                              //NorSum位数太多无法用于分组(位数多无法确定分组的 //可能性)int x = 0;int y = 0;                               //假设两个单独存在的数分别为x和yfor (i = 0; i < sz; i++)                 //利用和lowbit按位与的方式将数组元素分为两组{                                        //所有成对的数必定出现在同一组，x和y分别会位于不 //同组if ((Lowbit & (arr[i])) == 0)        //分别求两组数的异或和就可以得到x和y{ x ^= arr[i];}else{y ^= arr[i];}}

题解代码：

 

//方法二 位运算
//假设两个单独存在的数分别为x和y
int* FindNum2(int* arr, int sz)
{assert(arr);int* ptr = (int*)malloc(2 * sizeof(int)); //为存放查找结果的数组申请堆区上的空间if (ptr == NULL)                          //判断指针的有效性{perror("malloc failed\n");return NULL;}int i = 0;int NorSum = 0;                          //0异或x(x为任意值)结果为x，NorSum一定要初始化 //为0for (i = 0; i < sz; i++){NorSum ^= arr[i];                    //NorSum=x^y ,NorSum记录了x和y的不同位}int Lowbit = NorSum &(-NorSum);          /*取出NorSum中的最低位，该最低位可以将arr中的 //数分为两组*/                              //NorSum位数太多无法用于分组(位数多无法确定分 //组的可能性)int x = 0;int y = 0;for (i = 0; i < sz; i++)                 //利用和lowbit按位与的方式将数组元素分为两组{                                        //所有成对的数必定出现在同一组，x和y分别会位于 //不同组if ((Lowbit & (arr[i])) == 0)        //分别求两组数的异或和就可以得到x和y{ x ^= arr[i];}else{y ^= arr[i];}}ptr[0] = x;ptr[1] = y;return ptr;
}

该方法的时间复杂度是线性的:O(n)