136. 只出现一次的数字
题目描述
输入一个非空整数数组 nums。其中恰有一个值只出现一次，其他每个值都恰好出现两次。
返回那个只出现一次的值。
算法需要线性时间，并且只使用常数级的额外空间。
示例 1
输入：nums = [2,2,1] 输出：1
解释：2 出现两次，1 只出现一次。
示例 2
输入：nums = [4,1,2,1,2] 输出：4
解释：1 和 2 各出现两次，只有 4 出现一次。
示例 3
输入：nums = [1] 输出：1
数据范围
1 <= nums.length <= 3 * 10^4-3 * 10^4 <= nums[i] <= 3 * 10^4- 除一个值只出现一次外，其余值都恰好出现两次。
解题思路：异或抵消
利用异或满足交换律、结合律且 x^x=0、x^0=x，遍历累计即可。
为什么正确
累计值等于已扫描元素的异或结果，成对元素会互相抵消。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
异或只适用于每个重复元素恰好出现两次的约束，不能替代一般频次统计。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
from typing import List
class Solution:
def singleNumber(self, nums: List[int]) -> int:
value = 0
for num in nums:
value ^= num
return valueclass Solution {
public int singleNumber(int[] nums) {
int value = 0;
for (int num : nums) {
value ^= num;
}
return value;
}
}class Solution {
public:
int singleNumber(vector<int>& nums) {
int value = 0;
for (int num : nums) {
value ^= num;
}
return value;
}
};func singleNumber(nums []int) int {
value := 0
for _, num := range nums {
value ^= num
}
return value
}var singleNumber = function(nums) {
let value = 0;
for (const num of nums) {
value ^= num;
}
return value;
};function singleNumber(nums: number[]): number {
let value = 0;
for (const num of nums) {
value ^= num;
}
return value;
};其他解法
异或法空间 O(1)，是进阶要求的答案；哈希法更易想到，但要 O(n) 空间。
解法 2：哈希集合 时间 O(n)，空间 O(n)
遍历数组，用哈希集合记录出现过奇数次的数。第一次遇到就加入，第二次遇到就删除。遍历结束后集合里只剩下那个只出现一次的数。
思路直观，不依赖位运算性质。需要 O(n) 额外空间，不满足题目的常数空间进阶要求。
from typing import List
class Solution:
def singleNumber(self, nums: List[int]) -> int:
seen = set()
for num in nums:
if num in seen:
seen.remove(num)
else:
seen.add(num)
return seen.pop()class Solution {
public int singleNumber(int[] nums) {
Set<Integer> seen = new HashSet<>();
for (int num : nums) {
if (!seen.remove(num)) seen.add(num);
}
return seen.iterator().next();
}
}class Solution {
public:
int singleNumber(vector<int>& nums) {
unordered_set<int> seen;
for (int num : nums) {
if (seen.count(num)) seen.erase(num);
else seen.insert(num);
}
return *seen.begin();
}
};func singleNumber(nums []int) int {
seen := map[int]bool{}
for _, num := range nums {
if seen[num] {
delete(seen, num)
} else {
seen[num] = true
}
}
for num := range seen {
return num
}
return 0
}var singleNumber = function(nums) {
const seen = new Set();
for (const num of nums) {
if (seen.has(num)) seen.delete(num);
else seen.add(num);
}
return seen.values().next().value;
};function singleNumber(nums: number[]): number {
const seen = new Set<number>();
for (const num of nums) {
if (seen.has(num)) seen.delete(num);
else seen.add(num);
}
return seen.values().next().value as number;
}