zhangdizhangdi

136.只出现一次的数字

题目

LeetCode 简单

给你一个 非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现 线性时间复杂度 的算法来解决此问题，且该算法只使用 常量额外空间。

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

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

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

常量额外空间
算法在处理数据时，除了输入数组本身，只能用固定数量的额外变量（比如几个整数、指针、布尔值等），不能用与输入规模成比例增长的空间。

  • 可以： 用几个变量（如 int a, b, c），无论数组多大，变量数量都不变。
  • 不可以： 用数组、哈希表、集合等来存储和辅助查找（因为这些空间会随着输入规模变大而变大）。

题解

方法：哈希表

哈希表 O(n) O(n)

本题要求不使用额外的空间，因此本方法是不符合要求的。

js
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.values().next().value
}

const nums = [4, 1, 2, 1, 2]
console.log('🌰', singleNumber(nums))
执行结果
🌰 4

方法：位异或

位异或 O(n) O(1)

js
function singleNumber(nums) {
  let result = 0
  for (let i = 0; i < nums.length; i++) {
    result ^= nums[i]
    console.log('n', nums[i], 'r', result)
  }
  return result
}

const nums = [4, 1, 2, 1, 2]
console.log('🌰', singleNumber(nums))
执行结果
n 4 r 4
n 1 r 5
n 2 r 7
n 1 r 6
n 2 r 4
🌰 4