文章目录
1、题目描述2、解题思路2.1 哈希法2.2 位运算法
3、解题代码3.1 哈希法3.2 位运算法
4、解题心得
1、题目描述
【JZ40】一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。 知识点：数组，位运算，哈希 难度：☆
2、解题思路
2.1 哈希法
使用一个哈希map来记录每一个数字重复的次数，然后把重复次数为1的输出即可。 具体步骤： 1、定义一个HashMap<Integer, Integer>； 2、遍历数组，记录每个数字的出现次数； 3、定义一个Queue，把出现次数为1的数字入队； 4、队列出队即最终结果。
2.2 位运算法
异或操作是：两个位，不同则为1，相同则为0。 具有以下规律： 1、n^0 = 0; 2、n^n = 0; 3、n^n^m = n^(n^m)；满足交换律。 假设输入的数组array = {a,b,c,d,e,f,a,b,c,d}，其中字母表示数字。把array每一个数字都异或： int xor = a^b^c^d^e^f^a^b^c^d，根据交换律，等同于： int xor = (a^a)^(b^b)^(c^c)^(d^d)^(e^f),等同于： int xor = e^f 因此，数组所有数字进行异或的结果等同于不同的两个数字异或的结果。 下一步就是根据这个xor找出e和f分别是多少。 我们来分析这个xor，展开成二进制表示，肯定有些位为1，有些位为0。二进制的右侧为低位，左侧为高位。假设第3个位为1，那么可以推断：e和f的第3个二进制位肯定是一个为1，一个位0，不然异或结果不可能是1。 我们根据这个“第3个二进制位是否为1”作为条件，把array的数字分成两部分。那么，e和f肯定不会在一个部分里面，且相同数字肯定在一个部分里。 两部分数组分别为：arr1 = {a,a,c,c,e}和arr2 = {b,b,d,d,f}。 然后我们再分别把arr1和arr2异或一下： int xot_arr1 = a^a^c^c^e 根据异或特性，得xot_arr1 = e； int xot_arr2 = b^b^d^d^f 根据异或特性，得xot_arr2 = f； 即e和f都找到了。
3、解题代码
3.1 哈希法
package pers
.klb
.jzoffer
.medium
;
import java
.util
.*
;
public class NumsAppearOnce {
public void FindNumsAppearOnce(int[] array
, int num1
[], int num2
[]) {
HashMap
<Integer, Integer> map
= new HashMap<>();
for (int i
= 0; i
< array
.length
; i
++) {
if (map
.containsKey(array
[i
])) {
map
.put(array
[i
], map
.get(array
[i
]) + 1);
} else {
map
.put(array
[i
], 1);
}
}
Queue queue
= new LinkedList();
Set
<Integer> set
= map
.keySet();
for (Integer key
: set
) {
if (map
.get(key
) == 1) {
queue
.add(key
);
}
}
num1
[0] = (Integer
) queue
.poll();
num2
[0] = (Integer
) queue
.poll();
}
}
时间复杂度：O(N) 空间复杂度：O(N)
3.2 位运算法
package pers
.klb
.jzoffer
.medium
;
public class NumsAppearOnce {
public void FindNumsAppearOnce(int[] array
, int num1
[], int num2
[]) {
int xor
= 0;
for (int i
: array
) {
xor
^= i
;
}
int index
= 1;
while ((index
& xor
) == 0) {
index
= index
<< 1;
}
int result1
= 0;
int result2
= 0;
for (int j
: array
) {
if ((index
& j
) == 0) {
result1
^= j
;
} else {
result2
^= j
;
}
}
num1
[0] = result1
;
num2
[0] = result2
;
}
}
时间复杂度：O(N) 空间复杂度：O(1)
4、解题心得
类似这种找相同或找不同的数字，哈希法往往是最简单快捷的，笔试中优先考虑。在面试中，如果能够想出位运算的，说明基本功扎实，能给自己加分。
