面试题——找单独数字

布满荆棘的人生 2022-08-23 01:25 164阅读 0赞

数组A中，除了某一个数字x之外，其他数字都出现了三次，而x出现了一次。请给出最快的方法，找到x。

这道题是：数组中除了一个数字外，其他数字都出现了两次这道题的升级版，在其他数字都是两个的数组中找出单独的数字，由于两个相同的数字经过异或运算后为0，所以我们只要让数组中的每一个数字相互异或就能找到那个单独数字。

现在问题换成了其他数字都出现三次了，如果让数组中的数字都两两异或，出现三次的数相互异或就还是他本身，所以我们得换一种方式，但基本的思想都是相同的，就是通过位运算把出现三次的数对应位清零，剩下的位就是单独的数字的位了。

\[基本算法\]：

对于异或运算，是对应位重复出现两次，则将对应位置0.

现在问题换成了对应位出现三次则清零，我们可以这样做：

在重复出现两次的基础上，如果再出现一次，则总共出现了3次，

我们可以用一个变量计算某一位偶数次出现1，用另一个变量计算某一位奇数次出现1.

在上一次偶数次出现置1的基础上，下一次奇数次出现了后置1，那么这个出现三次的位就能被我们找到了。

我们使用另一个变量记录（偶数次出现和奇数次出现）变量的与后的值，就能得到出现三次的这些数字所对应的位出现1的数。

随后我们对其取反，将取反后的变量和出现奇数次的变量相与，就能找出单独出现的那个数字。

【代码如下】：

#include <stdlib.h>
    #include <stdio.h>
    
    int Find_Num(int *arr, int sz)
    {
    	int i;
    	int even = 0;   //统计偶数位上的数
    	int odd = 0;    //统计奇数位上的数
    	for (i = 0; i < sz; i++)
    	{
    		int is_three = 0;
    		even |= odd&arr[i];
    		odd ^= arr[i];
    		is_three = (even&odd);
    		even &= (~is_three);
    		odd &= (~is_three);
    	}
    	return odd;
    }
    int main()
    {
    	int arr[] = { 1, 2, 3, 1, 2, 3, 1, 2, 3, 4 };
    	int ret = Find_Num(arr, sizeof(arr) / sizeof(arr[0]));
    	printf("%d ", ret);
    	return 0;
    }