题目信息
示例1:
1
2
| 输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
|
示例2:
1
2
| 输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
|
注意
1
| 1. 2 <= nums.length <= 10000
|
解题思路
本题难点
查找数组中两个只出现一次的数字，性能最优。
具体思路
异或运算
- 交换律：p⊕q=q⊕p
- 结合律：p⊕(q⊕r)=(p⊕q)⊕r
- 恒等率：p⊕0=p
- 归零率：p⊕p=0
如果有若干个数字进行异或操作：根据 交换律、结合律 将相同的数字优先两两进行异或运算。此时就只剩下只出现一次的那个数了！
由于数组中存在着两个数字不重复的情况，我们将所有的数字异或操作起来，最终得到的结果是这两个数字的异或结果：(相同的两个数字相互异或，值为0)) 最后结果一定不为0，因为有两个数字不重复。
此时的难点在于，对两个不同数字的分组。
通过 & 运算来判断一位数字不同即可分为两组，那么我们随便两个不同的数字二进制上至少也有一位不同吧！
我们只需要找出那位二进制上不同的数字mask，即可完成分组（ & mask ）操作。
不同数字mask查找演示:
1
2
3
4
5
6
7
| num1: 101110 110 1111
num2: 111110 001 1001
num1^num2: 010000 111 0110
可行的mask: 010000 001 0010
010 0100
100
|
所有的可行 mask 个数，都与异或后1的位数有关。
提示：为了操作方便，我们只去找最低位的mask:
代码
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
26
| lass Solution {
public int[] singleNumbers(int[] nums) {
int k = 0;
for(int num : nums){
k ^= num;
}
int mask = 1;
while((mask & k) == 0){
mask <<= 1;
}
int a = 0;
int b = 0;
for(int num : nums){
if((num & mask) == 0){
a ^= num;
}else{
b ^= num;
}
}
return new int[]{a,b};
}
}
|
复杂度分析：
- 时间复杂度 O(N) ：只需要遍历数组两次。
- 空间复杂度 O(1) ： 只需要常数的空间存放若干变量。
其他优秀解答
解题思路
通过二分查找，将包含两不同数字的数组分组。
异或和为 0其实并不代表 要找的元素不在这里面，因为有可能 0只出现了 1次！ 所以这种思路需要特判一下某个数为 0的情况。
代码
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| class Solution {
public int[] singleNumbers(int[] nums) {
int sum = 0, min = Integer.MAX_VALUE, max = Integer.MIN_VALUE, zeroCount = 0;
for (int num: nums) {
if (num == 0) {
zeroCount += 1;
}
min = Math.min(min, num);
max = Math.max(max, num);
sum ^= num;
}
if (zeroCount == 1) {
return new int[]{sum, 0};
}
int lo = min, hi = max;
while (lo <= hi) {
int mid = (lo < 0 && hi > 0)? (lo + hi) >> 1: lo + (hi - lo) / 2;
int loSum = 0, hiSum = 0;
for (int num: nums) {
if (num <= mid) {
loSum ^= num;
} else {
hiSum ^= num;
}
}
if (loSum != 0 && hiSum != 0) {
return new int[] {loSum, hiSum};
}
if (loSum == 0) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return null;
}
}
|
