题目描述:

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

给定一个非空的整数数组,除了一个元素外,每个元素都会出现两次。找出那个单一的整数。

最常规的思路就是进行循环,统计出现的数字,只出现一次的就是我们要的答案了

for循环统计数字出现次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public int singleNumber(int[] nums) {
int[] result = new int[nums.length];
int count = 0;
for (int i = 0;i < nums.length; i++){
for (int j = 0;j <= count;j++){
if (j == count){
result[j] = -1;
count++;
j = count +1;
}else if (nums[i] == nums[j]){
result[j]++;
count++;
j = count + 1;
}
}
}
for (int k = 0; k < result.length ;k++){
if (result[k] == -1)
return nums[k];
}
return 0;
}
}

新建一个result数组用来存放统计的次数,初始值为-1,进行双重循环,以后每找到一个与nums数组中相同的数字,就在result数组中+1,即值变为0。最后根据result中值为-1(即在nums数组中没找到相同数值的数字)的数字就是我们要找的数字。

这种方法逻辑很顺,但是时间复杂度为O(n^2),运行时间会消费很多。
那么要降低时间复杂度,就得减少一层循环。怎么才能实现呢?既要实现统计次数,又要遍历数组,有应用过Map Reducer方法的同学应该很容易就能想到word count程序好像就是这么一个道理,因此我们可以使用Map进行存值判断。

Map实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int singleNumber(int[] nums) {
HashMap<Integer, Integer> result = new HashMap<>();
int resultNum = 0;
for(int i = 0; i < nums.length; i++){
int num = nums[i];
if(result.containsKey(num)){
result.remove(num);
}else{
result.put(num, i);
}
}
for (int res : result.keySet()) {
resultNum = res;
}
return resultNum;
}
}

因为nums数组中的重复数字只有两个,因此判断数字是否已经存在于Map中,若已经存在,则remove该数字,此时Map和nums数组中都已不存在该数字,若Map中不存在该数字,则put该数字。最后Map只剩下单一的数字,即我们想要的结果。

Map中需要插入key-value两个值,但是value的值对我们没有什么帮助,因此可以使用HashSet进一步优化。

HashSet实现

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public int singleNumber(int[] nums) {
HashSet<Integer> result = new HashSet<>();
for (int num : nums) {
if(!result.add(num))
result.remove(num);
}
Iterator<Integer> it = result.iterator();
return it.next();
}
}

判断nums中的数字是否已经存在与HashSet中,若已经存在,则remove,若不存在,则直接add。这步与Map类似,不过只需要插入一个nums数组中的值就够了。

上面都是常规的一些存储方法,可没想到还有一个更加简洁帅气的方法。就是使用异或 ^ 的方法。

XOR异或方法

1
2
3
4
5
6
7
8
9
class Solution {
public int singleNumber(int[] nums) {
int result = 0;
for (int num : nums) {
result = result ^ num;
}
return result;
}
}

什么意思呢,^ 异或满足下面的转化:

a b result
0 0 0
0 1 1
1 0 1
1 1 0

所以两个数字进行 ^ 运算时,先将数字转化为二进制,再进行 ^ 操作,当两个数字相同时,则对应的二进制数的位数也都相同,因此运算结果为0。当0与任意数字进行异或运算时,运算结果为该任意数字,因此最终的结果就是nums数组中出现的单一数字。