题目描述
落单的数I
给出2*n + 1 个的数字，除其中一个数字之外其他每个数字均出现两次，找到这个数字。
落单的数II
给出3*n + 1 个的数字，除其中一个数字之外其他每个数字均出现三次，找到这个数字。
落单的数III
给出2*n + 2个的数字，除其中两个数字之外其他每个数字均出现两次，找到这两个数字。
思路
落单的数系列题目因为是找落单的数，可以使用亦或。因为两个相同的数，亦或的结果为0
所以落单的数I 很容易就解决了
还可以把数组元素加入到hashmap，元素值作为key，元素出现的个数作为value，当value == 2时remove，最后遍历keyset把key输出即可
所以落单的数I II 很容易就解决了
落单的数III稍微复杂一点：
- 亦或一遍，可以找到两个落单的数的亦或值
- 找到这个值的二进制中第一个不为0的数的所在位，将该位为0的所有元素亦或一遍，该位所有为1的元素亦或一遍，就可以找到这两个落单的数
代码
1
2
3
4
5
6
7
8
9
10
| public int singleNumber(int[] A) {
if(A.length == 0) {
return 0;
}
int n = A[0];
for(int i = 1; i < A.length; i++) {
n = n ^ A[i];
}
return n;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public int singleNumberII(int[] A) {
int res = 0;
HashMap<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < A.length; i++) {
if(map.containsKey(A[i])) {
map.put(A[i], map.get(A[i])+1);
if(map.get(A[i]) == 3) {
map.remove(A[i]);
}
}else {
map.put(A[i], 1);
}
}
for(Integer key : map.keySet()) {
res = key;
}
return res;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| public List<Integer> singleNumberIII(int[] A) {
int res1 = A[0]; // 保存一遍亦或的结果
for(int i = 1; i < A.length; i++) {
res1 ^= A[i];
}
// 找到亦或的二进制数第一个不为0的数
int j = 1; // 第i位为1的值
while((res1 & j) == 0) {
j *= 2;
}
int res2 = 0; // 落单的数
int res3 = 0; // 落单的数
for(int num : A) {
if((num & j) == 0) {
res2 ^= num;
}else {
res3 ^= num;
}
}
List<Integer> list = new ArrayList<Integer>();
list.add(res2);
list.add(res3);
return list;
}
|
考察点