跳到主要内容

260.只出现一次的数字III

链接：260.只出现一次的数字III
难度：Medium
标签：位运算、数组
简介：给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。你可以按任意顺序返回答案。

题解 1 - typescript

编辑时间：2021-10-31
执行用时：84ms
内存消耗：41.2MB
编程语言：typescript
解法介绍：哈希。

function singleNumber(nums: number[]): number[] {
  const map = new Map<number, number>();
  nums.forEach(num => {
    map.set(num, (map.get(num) ?? 0) + 1);
  });
  return Array.from(map.entries())
    .filter(([, v]) => v === 1)
    .map(([k]) => k);
}

题解 2 - typescript

编辑时间：2021-10-31
执行用时：76ms
内存消耗：40.3MB
编程语言：typescript
解法介绍：位运算。

function singleNumber(nums: number[]): number[] {
  const xorNum = nums.reduce((ans, num) => ans ^ num, 0);
  let i = 0;
  while ((xorNum & (1 << i)) === 0) i++;
  let num1 = 0;
  let num2 = 0;
  for (const num of nums) {
    if (num & (1 << i)) num1 ^= num;
    else num2 ^= num;
  }
  return [num1, num2];
}

题解 3 - python

编辑时间：2023-10-16
执行用时：44ms
内存消耗：17.14MB
编程语言：python
解法介绍：所有数异或后a^b, 找两数不同的1。

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        v = reduce(lambda a, b: a ^ b, nums)
        v &= -v
        num1 = num2 = 0
        for num in nums:
            if v & num:
                num1 ^= num
            else:
                num2 ^= num
        return [num1, num2]

题解 1 - typescript
题解 2 - typescript
题解 3 - python