【剑指offer】面试题56(1):数组中只出现一次的两个数字
程序员文章站
2022-07-15 12:16:29
...
题目
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
思路
有空再补上 0.0
代码
/**
* 一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
*
* @author peige
*/
public class _56_01_NumbersAppearOnce {
/**
* num1,num2分别为长度为1的数组。传出参数将num1[0],num2[0]设置为返回结果
*/
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
if(array == null || array.length < 2)
return;
int n = 0;
for(int i = 0; i < array.length; ++i)
n ^= array[i];
int firstBitIs1 = findFirstBitIs1(n);
int N = 1 << firstBitIs1;
num1[0] = 0;
num2[0] = 0;
for(int i = 0; i < array.length; ++i) {
if((array[i] & N) != 0)
num1[0] ^= array[i];
else
num2[0] ^= array[i];
}
}
private int findFirstBitIs1(int n) {
if(n == 0)
return 0;
for(int i = 0; i < 32; ++i, n >>= 1) {
if((n & 1) == 1)
return i;
}
return 0;
}
}
测试
public class _56_01_Test {
public static void main(String[] args) {
test1();
test2();
}
private static void test1() {
int[] num1 = new int[1];
int[] num2 = new int[1];
_56_01_NumbersAppearOnce nao = new _56_01_NumbersAppearOnce();
nao.FindNumsAppearOnce(new int[] {55,2,3,1,1,2,55,6,7,6}, num1, num2);
System.out.println((num1[0] == 3 && num2[0] == 7) || (num1[0] == 7 && num2[0] == 3));
}
private static void test2() {
int[] num1 = new int[1];
int[] num2 = new int[1];
_56_01_NumbersAppearOnce nao = new _56_01_NumbersAppearOnce();
nao.FindNumsAppearOnce(new int[] {55,2}, num1, num2);
System.out.println((num1[0] == 55 && num2[0] == 2) || (num1[0] == 2 && num2[0] == 55));
}
}
上一篇: 题89:格雷编码
推荐阅读
-
剑指offer 56 数组中数字出现的次数 lintcode 82. 落单的数、83. 落单的数 II、84. 落单的数 III
-
【剑指offer】面试题56(1):数组中只出现一次的两个数字
-
剑指offer:数组中只出现一次的两个数字(java版)
-
剑指offer 面试题56 python版+解析:数组中只出现一次的两个数字,数组中唯一只出现一次的数字
-
剑指offer第二版-56.数组中只出现一次的两个数字
-
【算法分享】剑指offer56-数组中只出现一次的两个数字
-
剑指 Offer 56 - I. 数组中只出现一次的两个数字
-
剑指56:数组中只出现一次的数字——异或——位运算
-
《剑指Offer》Java刷题 NO.40 数组中只出现一次的数字(数组、HashMap、位运算、异或)
-
【剑指】56(1).数组中只出现一次的两个数字