题目描述
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
解法一：
由于出现了数字与次数这样的对应关系，很自然想到使用Map存储这个键值对，key存储数字，value存储次数。最后遍历Map找到只出现一次的数字即可。
时间复杂度为O（n），空间复杂度为O（n）。
public class Solution {
public static void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
boolean one = false;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0; i < array.length; i++) {
if(!map.containsKey(array[i])) {
map.put(array[i], 1);
}
else {
map.put(array[i], 2);
}
}
for(Entry m : map.entrySet()) {
if((int)m.getValue() == 1) {
if(one == false) {
num1[0] = (int) m.getKey();
one = true;
}
else {
num2[0] = (int) m.getKey();
}
}
}
}
}
解法二：
如果要求时间复杂度为O（n），空间复杂度为O（1）呢？很明显解法一便不符合要求。
这里涉及到位运算的知识。异或的性质是同一个数字与自己异或为0，与0异或为自己本身。
那么如果数组中只有一个只出现一次的数字的话，将数组从头开始异或，最后得到的便是只出现一次的数字，其他的数字在与自身异或的时候被消除掉了。
如果我们可以将题目提供的数组分成两部分，这两个子数组中均只含有一个只出现一次的数字，其他数字均出现两次。则问题便得到了解决。
设两个只出现一次的数字为a和b，将数组从头进行异或，最后得到的数字c一定不为0，因为该数字是a与b异或的结果，c中至少有一位1。取c中第一个为1的位的位置，根据这一位为1还是0将数组分为两部分，这样相同的数字一定在同一个子数组，a和b一定在两个子数组中。问题得到解决。
public class Solution {
public static void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
int product = 0;
int index = 0;
num1[0] = 0;
num2[0] = 0;
for(int i = 0; i < array.length; i++) {
product ^= array[i];
}
//获得第一个为1的位置
for(int i = 0; i < Integer.toBinaryString(product).length(); i++) {
if(Integer.toBinaryString(product).charAt(Integer.toBinaryString(product).length() - 1 - i) == '1') {
index = i;
break;
}
}
DecimalFormat df = new DecimalFormat("00000000000000000000000000000000");
for(int i = 0; i < array.length; i++) {
String binary = Integer.toBinaryString(array[i]);
String format = df.format(Integer.valueOf(binary)); //出错点
if(format.charAt(format.length() - 1 - index) == '1')
num1[0] ^= array[i];
else
num2[0] ^= array[i];
}
}
}
寻找第一个为1的位置时必须从右往左找，因为通过Integer.toBinaryString()函数产生的二进制位数是不固定的，例如1的二进制为1，而2的二进制为10，这就导致从右开始数得到的位数各个数字是不对应的。
上述程序在数字较小的时候可以正常工作，但是若出现较大的数字比如1000000时，转变为二进制为11110100001001000000，在“出错点”步骤会出现溢出错误。
实际上出错的关键是String format = df.format(Integer.valueOf(binary));这行，format函数输入不支持String所以我们把String转为int。该函数的目的是统一二进制的位数，我们可以通过别的方式来统一位数。
public class Solution {
public static void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
int product = 0;
int index = 0;
num1[0] = 0;
num2[0] = 0;
for(int i = 0; i < array.length; i++) {
product ^= array[i];
}
for(int i = 0; i < Integer.toBinaryString(product).length(); i++) {
if(Integer.toBinaryString(product).charAt(Integer.toBinaryString(product).length() - 1 - i) == '1') {
index = i;
break;
}
}
for(int i = 0; i < array.length; i++) {
String binary = Integer.toBinaryString(array[i]);
String tmp = "";
//通过循环对位数进行补足
if(binary.length() < 32) {
tmp = "";
for(int j = 0; j < 32 - binary.length(); j ++)
tmp += "0";
}
String format = tmp + binary;
if(format.charAt(format.length() - 1 - index) == '1')
num1[0] ^= array[i];
else
num2[0] ^= array[i];
}
}
}
上面的方法较为笨拙，位数补足的目的是为了便于判断相应位置是0还是1（若两个仅存在一次的数字a、b相异或的数字二进制为10，第一个为1的位置为2，判断数字4，二进制为100时不需要对100进行补足。但若a、b相异或的数字二进制为100，判断数字2，二进制为10时则需要对10进行补足。否则在从右往左判断的过程中10会溢出。）
我们可以通过位运算避免显式的位数补足。
public class Solution {
public static void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
int product = 0;
int index = 0;
num1[0] = 0;
num2[0] = 0;
for(int i = 0; i < array.length; i++)
product ^= array[i];
//获得第一个为1的位置
while((product & 1) == 0 && index < 8 * 4) {
product = product >> 1;
index++;
}
for(int i = 0; i < array.length; i++) {
//通过移位判断相应位置是否为1
if(((array[i] >> index) & 1) == 0)
num1[0] ^= array[i];
else
num2[0] ^= array[i];
}
}
}
1、通过依次右移1位和与1相与，可以很快得到第一个为1的位置，index < 8 * 4是因为JAVA中的int是32位的
2、通过直接右移index位并与1相与可以直接得到第index位是否为1
网友评论