• 周二. 6月 25th, 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;

}

   

《剑指offer解题报告(Java版)——数组中只出现一次的数字 40》有一个想法
  1. Wow, awesome blog layout! How long have you been blogging for?
    you make blogging look easy. The total look of your website is great, let alone the content material!
    You can see similar here e-commerce

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注