找出数组里的两个单身狗（异或的方法）

ahao

发布于 2024-03-19 18:54:11

2470

文章被收录于专栏：学习学习

题目描述

一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。编写一个函数找出这两个只出现一次的数字。例如：有数组的元素是：1，2，3，4，5，1，2，3，4，6 只有5和6只出现1次，要找出5和6 今天我们就用异或的方法来解决这个问题

首先我们来了解一下异或的使用方法

异或在C语言中是按二进制的原码进行按位的操作：例如： 1^2的结果是3

1的二进制：00000000 00000000 00000000 00000001
2的二进制：00000000 00000000 00000000 00000010
异或操作  ：00000000 00000000 00000000 00000011

这样我们就可以发现一个规律：

1：0与任何数字异或都等于那个数的本身
2：两个相同的数异或等于0

在之前的学习中我们可能遇到过找出数组中一个单身狗的问题，我们首先也来用异或解决这个问题

异或找一个单身狗

按照异或的规律，我们可以用以下的代码实现找出数组中只出现一次的一个数字：首先定义一个数ret为0，让它和数组中的每一个元素进行异或操作，最后得到的就是数组中只出现一次的数字（sz为数组的元素个数）。

int find_one_number(int* arr, int sz)
{
	int i = 0;
	int ret = 0;
	for (i = 0; i < sz; i++)
	{
		ret = ret ^ arr[i];
	}
	return ret;
}

例如：数组为1,1,2,2,3,4,4

0^1=1 --> 1^1=0 --> 0^1=1 --> 1^1=0 --> 0^2=2 --> 2^2=0 --> 0^3=3 -->  3^4^4 = 3^0 = 3

异或找两个单身狗

下面我们就来找两个单身狗的数组：一个数组中只有两个数字是出现一次，其他所有数字都出现了两次我们在了解了找一个单身狗的异或的解法后在这里就更加容易的理解了首先我们同样将整个数组异或：这个时候返回值ret就是两个只出现一次的数组的按位异或之后的值

int find_one_number(int* arr, int sz)
{
	int i = 0;
	int ret = 0;
	for (i = 0; i < sz; i++)
	{
		ret = ret ^ arr[i];
	}
	return ret;
}

然后我们再找出两个只出现一次的数异或之后的二进制位不同位的位置，将数组分为两个数组：在进行异或，就能分别得出两个单身狗了！找到有分歧的二进制位pos，并记录其位置

int pos;
 for (i = 0; i < 32; i++)
 {
  if ( ( ret >> i ) & 1 )
  //如果右移出来的这一位&1不等于0，那么这一位就是1
  {
   pos = i;
   break;
  }
 }

例如1 2 3 4 1 2，异或完的结果应该是3^4得到的111，那么随便找一位就行了。例如找最低位，那么这一位是1的有1 3 1，是0的有2 4 2，由于是利用异或结果为1的某一位分的组，所以两个待查询数字一定分别在两组中。所以再找两个变量，分别异或两组数，即可找到这两个数 pnum1用于异或末位为1的数字，pnum2用于异或末位为2的数字最后得出的pnum1就是末位为1的单身狗，pnum2就是末位为0的单身狗

*pnum1 = *pnum2 = 0;
 for (i = 0; i < sz; i++)
 {
  if ( ( arr[i]  >> pos ) & 1）//右移pos位得到的&1如果不等于0就是末位为1
  {
   *pnum1 ^= arr[i]; //将末位为1的异或
  }
  else
  {
   *pnum2 ^= arr[i]; //将末位为0的异或
  }
 }
}

完整代码如下：

void find_one_number(int* arr, int sz, int * pnum1, int * pnum2)
{
 int i = 0;
 int ret = 0;

 for (i = 0; i < sz; i++)
 {
  ret ^= arr[i];
 } 

 int pos;
 for (i = 0; i < 32; i++)
 {
  if ( ( ret >> i )  & 1 )
  {
   pos = i;
   break;
  }
 } 

 *pnum1 = *pnum2 = 0;
 for (i = 0; i < sz; i++)
 {
  if ( ( arr[i]  >> pos) & 1)
  {
   *pnum1 ^= arr[i]; 
  }
  else
  {
   *pnum2 ^= arr[i]; 
  }
 }
}

好了，今天的分享到这里就结束了，谢谢大家的支持！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-03-19，如有侵权请联系 cloudcommunity@tencent.com 删除

函数