题解 | #数组中只出现一次的两个数字#
数组中只出现一次的两个数字
http://www.nowcoder.com/practice/389fc1c3d3be4479a154f63f495abff8
位运算:对于数组中有两个不同的数字出现一次的情况,需要对其进行分组,首先需要找到这两个数字不相同的那个比特位,按照这个比特位进行分组
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @return int整型一维数组
*/
public int[] FindNumsAppearOnce (int[] array) {
// write code here
//位运算;两个数的情况下需要进行分组
int len = array.length;
if(len < 2) return new int[0];
int bitsum = 0;
for(int num : array){
bitsum ^= num;
}
//找到可以对两个数进行分组的那个比特位,由于前面进行了异或运算,两个不同的数不同的那个比特位就是最后异或结果第一个为1的比特位
int bitindex = 1;
// while(((bitsum>>bitindex)&1)==0){
// bitindex = bitindex<<1;
// }
while((bitindex&bitsum)==0){
bitindex<<=1;
}
int first = 0;
int second = 0;
for(int num : array){
if((num&bitindex)==0){
first ^= num;
}else{
second ^= num;
}
}
int[] res = new int[2];
if(first<second){
res[0] = first;
res[1] = second;
}else{
res[0] = second;
res[1] = first;
}
return res;
}
}