LeetCode-136.只出现一次的数字

发表于 分类于

题目描述

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

说明：

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

示例

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

题解

方法1：借助哈希表来实现

1
2
3
4
5
6
7
8
9
10
11
12
func singleNumber(_ nums: [Int]) -> Int {
  var map = [Int: Int]() // [value: index]
  for (index, value) in nums.enumerated() {
    if let _ = map[value]  {
      map.removeValue(forKey: value)
    } else {
      map[value] = index
    }
  }
  
  return map.first!.key
}

方法2：借助异或运算

1
2
3
4
5
6
7
func singleNumber2(_ nums: [Int]) -> Int {
  var res = nums[0]
  for value in nums.suffix(from: 1) {
    res ^= value
  }
  return res
}