Vue.js

Appearance

On this page

实战：只出现一次的数字 ​

这是位运算最经典的入门题——用异或的性质，一行代码解决。

题目描述 ​

LeetCode 136. 只出现一次的数字

给你一个非空整数数组 nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法，且使用常数空间来解决此问题。

示例 1：

输入：nums = [2,2,1]
输出：1

示例 2：

输入：nums = [4,1,2,1,2]
输出：4

示例 3：

输入：nums = [1]
输出：1

提示：

  • 1 ≤ nums.length ≤ 3 × 10⁴
  • -3 × 10⁴ ≤ nums[i] ≤ 3 × 10⁴
  • 除了某个元素只出现一次外，其余每个元素均出现两次

题目分析 ​

约束分析：

  • 线性时间 O(n)：不能排序（O(n log n)）
  • 常数空间 O(1)：不能用哈希表（O(n)）

普通方法行不通，需要用位运算。

异或运算回顾 ​

异或（XOR）的三个关键性质：

性质表达式说明
自反性a ^ a = 0相同的数异或为 0
零元素a ^ 0 = a任何数异或 0 是它本身
交换律/结合律a ^ b ^ a = b可以任意调换顺序

关键推论：一组数连续异或，成对的数会抵消，只留下出现奇数次的数。

a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b

解法 ​

把所有数异或在一起，成对出现的数会抵消，剩下的就是单独的数。

javascript
function singleNumber(nums) {
    let result = 0;
    
    for (const num of nums) {
        result ^= num;
    }
    
    return result;
}

一行代码版本（使用 reduce）：

javascript
function singleNumber(nums) {
    return nums.reduce((acc, num) => acc ^ num, 0);
}

执行过程 ​

以 nums = [4, 1, 2, 1, 2] 为例：

初始：result = 0

result ^= 4:  0 ^ 4 = 4      (二进制: 0000 ^ 0100 = 0100)
result ^= 1:  4 ^ 1 = 5      (二进制: 0100 ^ 0001 = 0101)
result ^= 2:  5 ^ 2 = 7      (二进制: 0101 ^ 0010 = 0111)
result ^= 1:  7 ^ 1 = 6      (二进制: 0111 ^ 0001 = 0110)
result ^= 2:  6 ^ 2 = 4      (二进制: 0110 ^ 0010 = 0100)

结果：4

为什么有效？

根据异或的交换律和结合律，可以重新排列：

4 ^ 1 ^ 2 ^ 1 ^ 2
= 4 ^ (1 ^ 1) ^ (2 ^ 2)    // 重新分组
= 4 ^ 0 ^ 0                 // 相同数异或为 0
= 4                         // 任何数异或 0 是它本身

边界情况 ​

javascript
// 只有一个元素
singleNumber([1]);  // 1

// 负数
singleNumber([-1, 1, 1]);  // -1

// 大数组
singleNumber([...Array(10000).fill(1), 2, ...Array(10000).fill(1)]);  // 2

常见错误 ​

错误一：初始值设错 ​

javascript
// 错误：初始值不是 0
let result = nums[0];
for (let i = 1; i < nums.length; i++) {
  result ^= nums[i];
}
// 这样也能工作，但不如 0 清晰

// 推荐：初始值为 0
let result = 0;
for (const num of nums) {
  result ^= num;
}

错误二：尝试用其他方法 ​

javascript
// 哈希表法：空间 O(n)，不满足要求
function singleNumber(nums) {
  const set = new Set();
  for (const num of nums) {
    if (set.has(num)) set.delete(num);
    else set.add(num);
  }
  return [...set][0];
}

// 排序法：时间 O(n log n)，不满足要求
function singleNumber(nums) {
  nums.sort((a, b) => a - b);
  for (let i = 0; i < nums.length; i += 2) {
    if (nums[i] !== nums[i + 1]) return nums[i];
  }
}

扩展：其他出现次数 ​

题目变体解法
其他出现 2 次，1 个出现 1 次全部异或（本题）
其他出现 3 次，1 个出现 1 次按位统计（LeetCode 137）
其他出现 2 次，2 个出现 1 次分组异或（LeetCode 260）

相关题目 ​

题目难度关键点
136. 只出现一次的数字简单本题
137. 只出现一次的数字 II中等其他出现3次
260. 只出现一次的数字 III中等两个只出现一次
268. 丢失的数字简单异或找缺失

总结 ​

  1. 核心性质：异或的自反性（a ^ a = 0）和零元素（a ^ 0 = a）
  2. 适用条件：其他元素出现偶数次
  3. 时间空间：O(n) 时间，O(1) 空间
  4. 一行代码：nums.reduce((acc, num) => acc ^ num, 0)

复杂度 ​

  • 时间：O(n)
  • 空间：O(1)

在 GitHub 上编辑此页