剑指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);
}
};