您的位置: 首页  >  文章  >  找出一个数组中只出现一个的数

找出一个数组中只出现一个的数

分类: 文章 • 2023-10-16 13:22:23

已知一个数组中，除了一个数字出现一次外，其他数字都出现两次，试找出这个数~~

思路分析：当看到这个题目，我就想，既然只有一个数出现一次，那么我们可以遍历这个数组，只要遇到相同的两

                   个数，就把它们置为一个比较大的数，最后输出那个没有被改变的数。

[objc] view plain copy
 找出一个数组中只出现一个的数找出一个数组中只出现一个的数
  1. #define _CRT_SECURE_NO_WARNINGS 1  
  2. #include<stdio.h>  
  3. int main()  
  4. {  
  5.     int arr[9];  
  6.     int i = 0;  
  7.     int j = 0;  
  8.     for (;i < 9;i++)  
  9.     {  
  10.         scanf("%d",&arr[i]);  
  11.     }  
  12.     for (i = 0;i < 8;i++)  
  13.     {  
  14.         for (j = i + 1;j < 9;j++)  
  15.         {  
  16.               
  17.             if ((arr[i] == (arr[i] & arr[j]) + ((arr[i] ^ arr[j]) >> 1)))  
  18.             {  
  19.                 arr[i] = 32767;  
  20.                 arr[j] = 32767;  
  21.             }  
  22.         }  
  23.     }  
  24.     for (i = 0;i < 9;i++)  
  25.     {  
  26.         if (32767 != arr[i])  
  27.             printf("%d",arr[i]);  
  28.     }  
  29.     system("pause");  
  30.     return 0;  
  31. }  
代码分析：

         代码缺陷：代码时间复杂度为o（n^2），还有将相同的数分别置成32767，我们不能保证数组中原本就没有                              这个 数。

         代码亮点：使用了一种比较高端的方法求出两数的平均值，这样就能防止数据过大，两数之和发生溢出。

   下边，我来重点解析这种求平均数的妙法~

找出一个数组中只出现一个的数

求平均数的另一种方法：

   a和b的平均数mid，mid = （a - b）/2+a;这种方法可以适用于任何类型数的平均数，而上述位运算的方法只能

    适用于整形数，且两个数的符号位相同的那种。

学习编程这么久，我们发现，经常一个题目有好多种方法，我们应该择优，也就是，我们的目的不是解决问题，

 而是更好的解决问题。上边求平均数的方法中，我们可以发现两个相同的数异或的结果是0，看看我们可否利用

这种方法解决呢？？

[objc] view plain copy
 找出一个数组中只出现一个的数找出一个数组中只出现一个的数
  1. #define _CRT_SECURE_NO_WARNINGS 1  
  2. #include<stdio.h>  
  3. int main()  
  4. {  
  5.     int arr[] = {1,2,3,4,1,2,5,3,5};  
  6.     int i = 0;  
  7.     int ret = 0;  
  8.     for (i = 0;i < sizeof(arr) / sizeof(arr[0]);i++)  
  9.     {  
  10.         ret ^= arr[i];  
  11.     }  
  12.     printf("%d",ret);  
  13.     system("pause");  
  14.     return 0;  
  15. }  
上述方法很好的利用了异或运算符，时间复杂度是O（n）。由于代码比较少，所以没有必要写成函数。

        如果一个数组中有两个数没有成对出现，其他数都成对，那么我们又是怎样找到这两个数呢？？

如果我们能将两个不同的数分开，然后利用上述找一个数的方法也可以找出这两个数。我们将实现方法写成函数的

形式。看以下代码：

[objc] view plain copy
 找出一个数组中只出现一个的数找出一个数组中只出现一个的数
  1. #define _CRT_SECURE_NO_WARNINGS 1  
  2. #include<stdio.h>  
  3. #include<assert.h>  
  4. void find_two_num(int arr[], int n, intint *p1, intint *p2)  
  5. {  
  6.     assert(p1);  
  7.     assert(p2);  
  8.     int i = 0;  
  9.     int ret = 0;//用来存储所有元素异或的结果  
  10.     int pos = 0;  
  11.     for (i = 0;i < n;i++)  
  12.     {  
  13.         ret ^= arr[i];  
  14.     }  
  15.     while (((ret >> pos) & 1)  != 1)  
  16.     {  
  17.         pos++;  
  18.     }  
  19.     for (i = 0;i < n;i++)  
  20.     {  
  21.         if (((arr[i] >> pos) &1) == 0)  
  22.         {  
  23.             *p1 ^= arr[i];  
  24.         }  
  25.     }  
  26.     *p2 = ret ^ *p1;  
  27. }  
  28. int main()  
  29. {  
  30.     int arr[] = {1,2,3,4,1,2,3,5};  
  31.     int num1 = 0;  
  32.     int num2 = 0;  
  33.     find_two_num(arr,8,&num1,&num2);  
  34.     printf("%d %d",num1,num2);  
  35.     system("pause");  
  36.     return 0;  
  37. }  

在以往的函数中，我们一般只需要一个返回值，而这个程序需要接受两个返回值，怎么办呢？？利用返回型参数。

 也就是传给函数的是存储数据的地址。

代码解析：我们的目标是将这个数组的元素分开，

    比如4,5只出现一次，100^101 = 001，我们根据为1的那一位也就是第0位是否为1将数据分成两组，相同的数必

然被分到一组，不同的数必将位于不同的组，然后将每个组异或就可得到结果~~

  我们没有必要将分的组的数保存起来，因为没有必要，只需要将组内的所有元素异或就行。

   还有，我们只要求出一个组的单独出现的数，只需要将两个数异或的结果（即为代码中的ret）异或已经求出的

出现一次的数就可以~推导如下：

    比如：a ^ b = m;

       则： a ^ b ^a = m^a;

              b = m ^a;

特别注意：位运算符 的优先级不太高（低于算术运算符的优先级），所以必要的时候不要吝啬括号哦~~

相关推荐