32-有两个单独的数字,其它数字成对,请输出这两个单独的数字

深碍√TFBOYSˉ_ 2022-12-22 04:57 11阅读 0赞

## 解题代码 ##

#include<stdio.h>
    
    //得到tmp二进制右数第一个1的值！！！
    //100->4; 10101->1; 1010->2
    int GetBit(int tmp)
    {
        
    	int i = 1;
    	for(int j=0;j<32;j++)
    	{
        
    		if((tmp & i) != 0)
    		{
        
    			break;
    		}
    		i <<= 1;
    	}
    	return i;
    }
    
    //有两个单独的数字,其它数字成对,请输出这两个单独的数字
    //分组:1.将两个单独数字分在不同组,2.相同数字一定在同一组
    //分组的办法:异或的结果的二进制右数第一个1作为分组依据 
    //右数的第一个1，说明这2个单独出现的数字在这个位上出现了不同，我们就可以分开了！
    void Num2(int *arr,int len)//O(n),O(1)
    {
        
    	int tmp = 0;
    	int x1 = 0; //第一个单独的数字
    	int x2 = 0;//第二个单独的数字
    	int flg = 0;//分组依据
    	for(int i=0;i<len;i++)//计算异或的值
    	{
        
    		tmp ^= arr[i];
    	}
    	//得到tmp二进制右数第一个1的值
    	flg = GetBit(tmp);
    	for(int i=0;i<len;i++)
    	{
        
    		if((arr[i]&flg) == 0) //分为两组数据,分别^
    		{
        
    			x1 ^= arr[i];
    		}
    		else
    		{
        
    			x2 ^= arr[i];
    		}
    	}
    	printf("%d,%d\n",x1,x2);
    }
    
    int main()
    {
        
    	int arr[] = {
        1,2,3,4,2,1,4,7};
    	Num2(arr,sizeof(arr)/sizeof(arr[0]));
    	return 0;
    }