手帐 Blog

主题

复盘 · LC 136 只出现一次的数字 ​

题目 ​

题意 ​

非空整数数组 nums：除一个元素外，其余每个元素都恰好出现两次。找出那个只出现一次的元素。

  • 必须线性时间；题目还要求尽量常数空间（面试常考）。
  • 边界：[1]、[2,2,1]、负数、答案在中间。

涉及算法 ​

标签一句话
哈希表 / Map出现一次放入，再遇到就删；最后剩下的即答案
异或（XOR）a ^ a = 0，a ^ 0 = a；全员异或后只剩单身那个

教程对照：数组手感见 04 · 数组基础题手感；哈希用法见 09 · 哈希表进阶。位运算本题是面试加分项，系列里没有专篇，默写 XOR 即可。

评价我的解法 ​

你的思路：Map 当「奇数次出现」集合——第一次 set，第二次 delete，扫完 Map 里只剩单身元素。在「其余都出现两次」的前提下完全正确，而且比「先全量计数再扫一遍找 count===1」更省一点中间状态。

我的代码（摘自 136-只出现一次的数字/index.js，不含本地测例）：

javascript
var singleNumber = function (nums) {
  const oneMap = new Map();
  for (let i = 0; i < nums.length; i++) {
    const val = nums[i];
    const count = oneMap.get(val);
    if (count) {
      oneMap.delete(val);
    } else {
      oneMap.set(val, 1);
    }
  }
  let res = 0;
  oneMap.forEach((val, key) => {
    res = key;
  });
  return res;
};

务实评价：

  1. 正确性：约束满足时必过；if (count) 在本写法里等价于「已在 Map」（值恒为 1），没问题。
  2. 复杂度：时间 O(n)，空间最坏 O(n)——没达到题目「常数空间」的偏好。
  3. 取答案略绕：为拿唯一 key 写了 forEach；更干净是 return oneMap.keys().next().value，或循环里维护 res。
  4. 面试口述：Map 版能讲清，但面试官多半会追问「O(1) 空间」→ 必须会 XOR。

小结：哈希解法合格、思路清晰；缺的是位运算那一刀。

最佳题解 ​

全数组异或：

javascript
/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  let x = 0;
  for (let i = 0; i < nums.length; i++) {
    x ^= nums[i];
  }
  return x;
};
  • 时间 O(n)，空间 O(1)。
  • 为何更优：成对抵消成 0，只剩单身；无额外表。

若坚持哈希，也可用 Set：见过则 delete，未见则 add，最后 Set 里剩一个——和你今天的 Map 同套路，空间同阶。

关联题目 ​

题为何相关
137. 只出现一次的数字 II其余出现三次；位计数 / 状态机
260. 只出现一次的数字 III两个单身；XOR 分组
268. 丢失的数字也可用 XOR / 求和差

一句话带走 ​

其余都成对出现 → 全体异或；哈希是保底，O(1) 空间才是面试答案。