【LeetCode题解】136_只出现一次的数字
目录
描述
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
方法一：列表操作
思路
新建一个变量（列表对象），遍历数组中的所有元素，如果元素在列表中存在，则删除该元素；如果元素在列表中不存在，则向列表中添加该元素。最后，列表中剩余的唯一元素就是我们找的唯一只出现一次的数字。
Java 实现
class Solution {
public int singleNumber(int[] nums) {
List<Integer> list = new LinkedList<>();
for (int num : nums) {
if (list.contains(num)) {
list.remove(new Integer(num));
} else {
list.add(num);
}
}
return list.get(0);
}
}
复杂度分析：
- 时间复杂度：\(O(n^2)\)
- 空间复杂度：\(O(n)\)
Python 实现
class Solution:
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l = list()
for num in nums:
if num in l:
l.remove(num)
else:
l.append(num)
return l.pop()
# 超出时间限制
复杂度分析同上。
方法二：哈希表
思路
思路和方法一相同，只是存放数据的容器改用哈希表，由于哈希表查询操作的时间复杂度是 \(O(1)\) 的，因此，算法最终的时间复杂度降为 \(O(n)\)。
Java 实现
class Solution {
public int singleNumber(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
if (map.containsKey(num)) {
map.remove(num);
} else {
map.put(num, 1);
}
}
return map.entrySet().iterator().next().getKey();
}
}
复杂度分析：
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
Python 实现
class Solution:
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
d = dict()
for num in nums:
try:
d.pop(num)
except:
d[num] = 1
return d.popitem()[0]
复杂度分析同上。
方法三：数学运算
思路
由于数组中的数字除了唯一一个数字只出现一次外，其余都是出现两次的，因此，如果我们将所有的数字乘以 2 再减去数组中所有的元素，则可以得到只出现一次的数字，即
\[2 * (a_1 + a_2 + \ldots + a_n + a_x) - (a_1 + a_1 + \ldots + a_n + a_n + a_x) = a_x
\]
\]
其中，\(a_1\) 到 \(a_n\) 是出现两次的数字，\(a_x\) 则是出现两次的数字。
Java 实现
class Solution {
public int singleNumber(int[] nums) {
Set<Integer> set = new HashSet<>();
int arraySum = 0;
for (int num : nums) {
set.add(num);
arraySum += num;
}
int doubleSum = 0;
for (int num : set) {
doubleSum += (2 * num);
}
return doubleSum - arraySum;
}
}
复杂度分析：
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
Python 实现
class Solution:
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return 2 * sum(set(nums)) - sum(nums)
复杂度分析同上。
方法四：位运算
思路
先来回顾一下两个位运算：
- 任何数与 0 异或都不改变它的值，即 \(a \oplus 0 = a\)
- 任何数与其自身异或都为 0，即 \(a \oplus a = 0\)
假设题目中描述的数组为 \([a_1,\, a_1,\, a_2,\, a_2,\, \ldots,\, a_n,\, a_n,\, a_x]\) ，其中，\(a_x\) 只出现一次，其余的元素都出现两次。对该数组中的所有元素进行异或运算可得，
\[\begin{align*}
& \,\,a_1 \oplus a_1 \oplus \ldots \oplus a_n \oplus a_n \oplus a_x \\
= & \,\,(a_1 \oplus a_1) \oplus \ldots \oplus (a_n \oplus a_n) \oplus a_x \\
= &\,\, 0 \,\oplus \ldots \oplus 0 \,\oplus a_x \\
= &\,\, a_x
\end{align*}
\]
& \,\,a_1 \oplus a_1 \oplus \ldots \oplus a_n \oplus a_n \oplus a_x \\
= & \,\,(a_1 \oplus a_1) \oplus \ldots \oplus (a_n \oplus a_n) \oplus a_x \\
= &\,\, 0 \,\oplus \ldots \oplus 0 \,\oplus a_x \\
= &\,\, a_x
\end{align*}
\]
因此，只需要遍历数组中的所有元素，依次进行两两异或操作就可以找出只出现一次的元素。
Java 实现
class Solution {
public int singleNumber(int[] nums) {
int ret = nums[0];
for (int i = 1; i < nums.length; ++i) {
ret ^= nums[i];
}
return ret;
}
}
复杂度分析：
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(1)\)
Python 实现
class Solution:
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
ret = 0
for num in nums:
ret ^= num
return ret
复杂度分析同上。