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