NowCoder 数组中只出现一次的数字 异或运算
程序员文章站
2022-07-15 12:13:21
...
题意:一个数组中有两个数字只出现了一次,其他都出现了两次,找出这两个数字
思路:用Map存储数字出现次数复杂度也不高,但是没有完全按照题意要求来做,正确的做法是用异或运算,将数组中所有数字异或起来,所有相同的数字会抵消,只剩下两个只出现一次的不同的数字,这时可以找到异或结果二进制中第一个1,把原数组划分成两个子数组,即在那位带1和不带1的,之后再次在两个数组异或求出两数
public class Solution {
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
int ans = array[0];
for (int i = 1; i < array.length; i++)
ans ^= array[i];
int temp = ans, cnt = 0;
while (temp%2 != 1) {
temp >>= 1;
cnt++;
}
int j = 0, k = 0;
int[] t1 = new int[array.length];
int[] t2 = new int[array.length];
for (int i = 0; i < array.length; i++) {
if ((array[i]&((int)Math.pow(2, cnt))) != 0)
t1[j++] = array[i];
else
t2[k++] = array[i];
}
num1[0] = t1[0]; num2[0] = t2[0];
for (int i = 1; i < j; i++)
num1[0] ^= t1[i];
for (int i = 1; i < k; i++)
num2[0] ^= t2[i];
return;
}
}
上一篇: LintCode-40.用栈实现队列
下一篇: tornado 登录状态保持