• 周日. 10 月 6th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

剑指offer解题报告(Java版)——数组中只出现一次的数字 40

admin

11 月 28, 2021

   

分析问题

   

任何一个数字异或它自己都等于0,通过这个思想遍历数组,用一个result累计异或操作,如果遇到某一个数两次,必定消除了异或操作,换句话说就是如果我们从头依次异或数组中的每一个数字,那么最终的结果应该是那个只出现一次的数字

   

要想说的更明白一点不如举个例子

   

实例

   

比如int[] array={4,5,5};我们声明一个result=0,然后依次用result去异或array中的每一个数,result异或4,结果为0100,接着异或5,结果为0001,接着异或5,结果为0100,即找出了4

   

问题转换

   

而实际的问题是有两个只出现一次的数,如何转换呢,我们就需要把数组分为两组,每组都只有一个,不就可以了

   

比如int[] array={2,4,3,6,3,2,5,5};我们声明一个result=0,然后依次用result去异或array中的每一个数,result异或2,结果为0010,接着异或4,结果为0110,接着异或3,结果为0101,接着异或6,结果为0011,接着异或3,结果为0000,接着异或2,结果为0010,接着异或5,结果为0111,接着异或5,结果为0010

   

int result=0;

for(int i:array)

result^=i;

   

这个结果对我们有什么用呢,我们可以根据结果的倒数第二位是否为1,将数组分为两组,分别对两个子数组求异或,即可得到两个子数组中只出现一次的数,这里需要声明两个result,这里我们用number1和number2替代

   

int number1=0,number2=0;

for(int i:array)

{

if(isBit1(i, index))

number1^=i;

else

number2^=i;                

}

System.out.println(number1);        

System.out.println(number2);

   

其中isBit1是判断一个数的index位上是否为1

   

private boolean isBit1(int number,int index)

{

number=number >> index;

return (number & 1)==0;

}

   

   

另外这里我们是知道分数组的结果是倒数第二个为1,然后实际应用中我们需要一个函数告诉我们倒数第几个为1,

   

private int findFirstBitIs1(int number)

{

int indexBit=0;

while((number & 1)==0)

{

number=number >> 1;

++indexBit;

}

return indexBit;

}

   

发表回复