导航
导航
文章目录
  1. 题目
  2. 翻译
  3. 拓展
    1. 方法一
    2. 方法二
    3. 方法三

LeetCode-136.Single Number

题目

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

翻译

给出一个整数数组,其中除了一个元素外,其他元素均出现了两次。找出单身的那个。
注意:你的算法的时间复杂度应当时线性的。你可以不使用额外空间实现吗?

题目要求线性运行时间,并且不使用额外空间,因此利用异或运算。
根据异或运算的特性:
A. a ^ b = b ^ a
B. 0 ^ a = a
C. 0 ^ 0 = 0
可得出结论:将所有数字逐一进行异或,即可得结果:

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

Runtime: 2 ms

拓展

方法一

逐个比较,时间复杂度O(n2),空间复杂度O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public int singleNumber(int[] nums) {
int len = nums.length;
for (int i = 0; i < len; i++) {
int j = 0;
for ( ; j < len; j++)
if (nums[i] == nums[j] && i != j) break;
if (j == len) return nums[i];
}

return nums[len - 1];
}
}

Runtime: 117 ms

方法二

维护一个List,开始为空,出现未包含数字则加入,再次出现则删除,最后剩下一个元素即是。时间复杂度O(1),空间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
public int singleNumber(int[] nums) {
List<Integer> numRecord = new ArrayList<Integer>();
for (int num : nums) {
int index = numRecord.indexOf(num);
if (index == -1) numRecord.add(num);
else numRecord.remove(index);
}

return numRecord.get(0);
}
}

Runtime: 193 ms

方法三

先排序,此时有三种情况:A.唯一数字在头部;B.唯一数字在尾部;C.唯一数字在中间,分别判断即可。时间复杂度O(nlgn)(取决于排序),空间复杂度O(n)(不影响原数组情况下)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
public int singleNumber(int[] nums) {
int len = nums.length;
if (len == 1) return nums[0];
int[] sortedNums = Arrays.copyOf(nums, len);
Arrays.sort(sortedNums);
if (sortedNums[0] != sortedNums[1]) return sortedNums[0];
if (sortedNums[len - 1] != sortedNums[len - 2]) return sortedNums[len - 1];
for (int i = 1; i < len - 1; i++) {
if (sortedNums[i - 1] != sortedNums[i] && sortedNums[i] != sortedNums[i + 1]) return sortedNums[i];
}

return 0;
}
}

Runtime: 8 ms

参考:
http://www.cnblogs.com/changchengxiao/p/3413294.html
http://www.powerxing.com/leetcode-single-number/