欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指offer-----数组-----数组中只出现一次的数字

程序员文章站 2022-07-15 10:52:32
...

题目:数组中数字出现的次数

一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度O(n),空间复杂度O(1)。

思路标签:

  • 算法:问题分步解决
  • 异或

解答:

  • 使用异或运算的一个性质:任何一个数字异或它自己都等于0;那么如果从头到尾依次异或数组中的每个数,最终即是只出现依次的数字;
  • 题中需要寻找两个只出现一次的数字,那么我们如果将原数组分成两个子数组,每个子数组中只包含一个数字,其他数字都是成对出现。
  • 首先对所有元素进行异或,得到的结果是两个只出现一次的数字异或的结果,因为两个数字不一样,所以异或的结果中肯定至少有一位1;
  • 我们以第一个1的位置是否出现1为划分,将数组分为两个子数组;
  • 分别对每个子数组进行元素异或,则可以得到两个只出现一次的数字。
  • 注意:不必进行子数组的分拆和组合,只要在第二次遍历整个数组的过程中,对每个元素进行一次属于哪个子数组的判断操作即可。
class Solution
{
public:
	void FindNumsAppearOnce(vector<int>data,int* num1,int* num2)
	{
		int length = data.size();
		if(length<2)
			return;
			
		//对原始数据求异火
		int resultExclusiveOR=0;
		for(int i=0;i<length;i++)
		{
			resultExclusiveOR^=data[i];
		}
		
		unsigned int index0f1=FindFirstBitIs1(resultExclusiveOR);
		
		*num1=*num2=0;
		for(int j=0;j<length;j++)
		{
			if(IsBit(data[j],index0f1))
				*num1^=data[j];
			else
				*num2^=data[j];
		}
	}
	
private:
	//找到二进制数num第一个为1的位数,比如0010,第一个位移的位数2
	unsigned int FindFirstBitIs1(int num)
	{
		unsigned int indexBit=0;
		//只判断一个字节
		while((num&1)==0&&(indexBit<8*sizeof(unsigned int)))
		{
		num=num>>1;
		indexBit++;
		}
		return indexBit;
	}
	//判断第indexBit是否为一
	bool IsBit(int num,unsigned int indexBit)
	{
		num=num>>indexBit;
		return (num&1);
		
	}
	
};