剑指offer(40)数组中只出现一次的两个数字
程序员文章站
2022-03-08 16:23:22
...
/**
* 题目:数组中数字出现的次数。数组中只出现一次的两个数字,要求空间o(1)时间o(n). eg:{2,4,3,6,3,2,5,5}结果是4、6
* 思路:剑指offer 异或思想,任何数和它本身异或的值为0.
* 我们依旧从头到尾异或每个数字,那么最终的结果就是这两个只出现一次的数字的异或结果,由于两个数不同,因此这个结果数字中一定有一位为1,把结果中第一个1的位置记为第n位。
* 因为是两个只出现一次的数字的异或结果,所以这两个数字在第n位上的数字一定是1和0。
* eg:对每个数字进行异或得到结果0010,根据倒数第二位是不是1将数组分成2组{2,3,6,3,2}和{4,5,5} 再分别对两个子数组求异或
*
* @author hexiaoli
*/
public class Main {
public static int[] FindNumsAppearOnce(int[] array) {
// 边界
if (array.length < 2 || array == null) {
return null;
}
int resultExclusiveOR = 0;
int length = array.length;
for (int i = 0; i < length; i++) {
resultExclusiveOR ^= array[i];
}
// 首次出现1的情况
int indexOf1 = 0;
while (((resultExclusiveOR & 1) == 0) && (indexOf1 <= 4 * 8)) {
resultExclusiveOR = resultExclusiveOR >> 1;
indexOf1++;
}
int result[] = new int[] { 0, 0 };
// 分为两组
for (int i = 0; i < length; i++) {
if (((array[i] >> indexOf1) & 1) == 1)
result[0] ^= array[i];
else
result[1] ^= array[i];
}
return result;
}
public static void main(String[] args) {
int[] array = new int[] { 2, 4, 3, 6, 3, 2, 5, 5 };
int[] result = FindNumsAppearOnce(array);
System.out.println(result[0] + " and " + result[1]);
}
}