【知识迁移能力】数组中只出现一次的数字
程序员文章站
2022-07-15 12:40:24
...
此题出自牛客网的剑指offer专题
题目描述
一个整型数组里除了两个数字之外,其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字。
解题思路
这道题一开始完全是一脸懵逼的,还想着传进来的那两个数组有什么用,而且函数还没返回值。。。后面看了一下别人的题解才稍微有点眉目。。。原来那两个数组是用来存结果的。。。
首先:位运算中异或的性质:两个相同数字异或=0,一个数和0异或还是它本身。
当只有一个数出现一次时,我们把数组中所有的数,依次异或运算,最后剩下的就是落单的数,因为成对儿出现的都抵消了。
按照这个思路我们可以从头到尾依次异或数组中的每一个数字,那么最终得到的结果就是两个只出现一次的数字的异或结果。因为其它数字都出现了两次,在异或中全部抵消掉了。由于这两个数字肯定不一样,那么这个异或结果肯定不为0 ,也就是说在这个结果数字的二进制表示中至少就有一位为1 。我们在结果数字中找到第一个为1 的位的位置,记为第N 位。现在我们以第N 位是不是1 为标准把原数组中的数字分成两个子数组,第一个子数组中每个数字的第N 位都为1 ,而第二个子数组的每个数字的第N 位都为0 。
现在我们已经把原数组分成了两个子数组,每个子数组都包含一个只出现一次的数字,而其它数字都出现了两次。因此到此为止,所有的问题我们都已经解决。
实现代码
Java版本
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
if(array==null || array.length<2){
return;
}
//拿到目标值的异或结果
int temp = 0;
for(int i=0;i<array.length;i++){
temp ^=array[i];
}
//取temp值二进制第一个为1的位置(从右往左)
int index=getFirstOne(temp);
//进行分组
for(int i=0;i<array.length;i++){
if(judge(array[i],index)){
num1[0] ^= array[i];
} else {
num2[0] ^= array[i];
}
}
}
public int getFirstOne(int num){
int index=0;
while(((num&1)==0) && index<32){
num = num>>1;
index++;
}
return index;
}
public boolean judge(int num,int index){
num = num>>index;
return (num&1)==1;
}
}
C++版本
class Solution {
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
if(data.size()<2)
{
return;
}
//遍历数组拿到两个目标值的异或结果
int temp=0;
for(int i = 0;i< data.size();i++)
{
temp = temp^data[i];
}
//此时temp存储的是两个目标值的异或结果
int index = getFirstOne(temp);
//进行分组
for(int i=0;i<data.size();i++)
{
if(judge(data[i],index))
{
(*num1) = (*num1)^data[i];
}
else
{
(*num2) = (*num2)^data[i];
}
}
}
//拿到temp值二进制的第一个为1的位置(从右到左)
int getFirstOne(int temp)
{
int index=0;
while(((temp&1)==0) && index<32)
{
temp=temp>>1;
index++;
}
return index;
}
//判断num的二进制的index位是否为1
bool judge(int num,int index)
{
num = num>>index;
return (num&1)==1;
}
};
上一篇: 2011清华考研机试题1
下一篇: DDD领域模型分析