likes
comments
collection
share

算法(TS):只出现一次的数字

作者站长头像
站长
· 阅读数 14

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

你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。

上题要求时间复杂度为 O(n),空间复杂度为O(1)

解法一:维护一个 Map 对象

创建一个空的 Map 对象,遍历数组 nums,每遍历出一个 num,便在 Map 对象中查找是否存在它,不存在则加入 Map 并将值设置为 1,存在则将值设为 -1,等数组遍历结束,Map 对象中值为1的数字就是只出现一次的数字。

function singleNumber(nums: number[]): number {
  const uniqueMap = new Map<number,number>()
  for (const num of nums) {
    if (uniqueMap.has(num)) {
      uniqueMap.set(num,-1)
    } else {
      uniqueMap.set(num,1)
    }
  }
   const unique = [...uniqueMap].find(([_,k]) => k === 1)
  return unique![0];
}

存在一次遍历数组,因此时间复杂度为 O(n),空间复杂度为O(n)

解法二:位运算符(异或)

异或运算符有下面 3 个特性

  1. a ^ 0 = a,即,任何数与数字 0 异或,得到的结果都等于它本身
  2. a ^ a = 0,即,任何数与自身异或,得到的结果都等于 0
  3. a ^ b ^ c = a ^ c ^ b,异或运算符,满足交换率

遍历 nums,让数组中的数字两两异或,最终得到的结果便是数组中只出现一次的数字

function singleNumber(nums: number[]): number {
  let uniqueNumber = 0

  for (const num of nums) {
    uniqueNumber ^= num
  }

  return uniqueNumber
}

存在一次遍历数组,因此时间复杂度为 O(n),没有额外的中间量空间复杂度为O(1)

转载自:https://juejin.cn/post/7298674250965155877
评论
请登录