序列中只有一个数出现了一次,其余均出现了两次,找出只出现过一次的这个数
序列中只有一个数出现了一次,其他均出现了两次,找出只出现过一次的这个数
例如:{10,9,8,7,6,6,7,8,9,10,5}
其中只有5出现了一次,其他的数均出现了两次,请找出这个数:5。
首先出现在我们脑海中的是最基本的方法:已知只有一个数出现过一次,那么只要嵌套两次循环就能找出只出现过一次的那个数,将他返回。
代码如下:
public static Integer findOnlyNum(int[] array){ for(int i = 0 ;i<array.length;i++){ int j = 0; for(;j<=array.length;j++){ if(i==j){ continue; } if(j==array.length){ break; } if(array[i]==array[j]){ break; } } if(j==array.length){ return array[i]; } } return null; }
这个方法在时间复杂度上属于T(n^2),那么有没有更好的方法能够实现上述的功能呢?
在计算机原理中我们接触到一个位操作符:^
相同的结果会得到全0;和全0异或,结果不变;和全1异或,结果会得到自己的取反。
我们需要证明的是a^b^a^b=(a^a)^(b^b),这一点参照计算机原理。
那么我们的代码就可以简化成:
public static Integer findOnlyNum1(int[] array){ int result = 0; for(int i = 0 ;i<array.length;i++){ result^=array[i]; } return result; }