简单

问题描述

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

进阶：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

提示：

• 1 <= nums.length <= 3 * 104
• -3 _ 104 <= nums[i] <= 3 _ 104
• 数组中除了某个元素只出现一次以外，其余每个元素均出现两次

排序

排序后，相同的元素会相邻，找出相邻不相等的元素即可。

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  nums.sort((a, b) => a - b)
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === nums[i + 1]) i++
    else return nums[i]
  }
}

• 时间复杂度：$O(n\;log\;n)$
• 空间复杂度：$O(log\;n)$

词频统计

使用哈希表对数组中数字个数进行统计，最后返回个数为 $1$ 的数字。

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  const map = new Map()
  for (const num of nums) {
    map.set(num, (map.get(num) || 0) + 1)
  }
  for (const [k, v] of map.entries()) {
    if (v === 1) return k
  }
  return -1
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

位运算

异或运算有以下性质：

• $a \oplus a = 0$
• $a \oplus 0 = a$
• $a \oplus b \oplus c = a \oplus c \oplus b$

对数组中所有数字进行异或运算后，最终答案即为出现 $1$ 次的数字。

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  return nums.reduce((ans, num) => ans ^ num, 0)
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$