来源Leetcode第136题只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
链表
最开始是想用哈希表来做的，但是还是有点不熟，就用了一个链表，然而在查找结点，删除结点上花费了太多的时间复杂度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public int singleNumber2(int[] nums) {
if(nums.length == 0)
return 0;
int lenth = nums.length;
List<Integer> flag = new LinkedList<>();
for(int i = 0; i < lenth ; i++){
if(i == 0){
flag.add(nums[i]);
continue;
}
else if(flag.contains(nums[i])){
int pos = flag.indexOf(nums[i]);
flag.remove(pos);
}
else
flag.add(nums[i]);
}
return flag.get(0);
}
|
排序
利用快速排序，在一次遍历找到落单的元素，然而还是很慢
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public int singleNumber(int[] nums) {
if(nums.length == 0)
return 0;
Arrays.sort(nums);
for(int i = 0;i < nums.length;){
if(i == nums.length - 1)
return nums[i];
else if(nums[i] == nums[i + 1])
i +=2;
else if(nums[i] != nums[i + 1])
return nums[i];
}
return 0;
}
|
哈希表
来源题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public int singleNumber(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (Integer i : nums) {
Integer count = map.get(i);
count = count == null ? 1 : ++count;
map.put(i, count);
}
for (Integer i : map.keySet()) {
Integer count = map.get(i);
if (count == 1) {
return i;
}
}
return -1;
}
|
异或
在电路和汇编里见到过的，利用异或求单一的一个数
1
2
3
4
5
6
7
8
9
| public int singleNumber(int[] nums) {
int ans = nums[0];
if (nums.length > 1) {
for (int i = 1; i < nums.length; i++) {
ans = ans ^ nums[i];
}
}
return ans;
}
|