【Day 71 】2024-06-17 - 260. 只出现一次的数字 III

[azl397985856]

260. 只出现一次的数字 III

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/single-number-iii/

前置知识

• 位运算
• 数组
• 哈希表

  题目描述

  
  给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。

示例 :

输入: [1,2,1,3,2,5] 输出: [3,5] 注意：

结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

[lxy1108]

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        vals = set()
        for n in nums:
            if n in vals:
                vals.remove(n)
            else:
                vals.add(n)
        return list(vals)

[luzhaofeng]

class Solution(object):
  def singleNumber(self, nums):
      xor_sum = 0
      for num in nums:
          xor_sum ^= num
      # lsb = xorsum & (-xorsum)
      cls = xor_sum - (xor_sum & (xor_sum-1))
      x1 = x2 = 0
      for num in nums:
          if num & cls:
              x1 ^= num
          else:
              x2 ^= num

      return [x1, x2]

[franklinsworld666]

代码

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        diff = 0
        for n in nums:
            diff ^= n
        diff &= -diff

        res = [0, 0]
        for n in nums:
            if(n&diff==0):
                res[0] ^= n
            else:
                res[1]^=n

        return res

[zhiyuanpeng]

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        xor = 0
        for val in nums:
            xor ^= val
        mask = 1
        while mask & xor == 0:
            mask <<= 1
        a, b =0, 0
        for val in nums:
            if val & mask:
                a ^= val
            else:
                b ^= val
        return [a, b]

[Dtjk]

var singleNumber = function(nums) { const freq = new Map(); for (const num of nums) { freq.set(num, (freq.get(num) || 0) + 1); } const ans = []; for (const [num, occ] of freq.entries()) { if (occ === 1) { ans.push(num); } } return ans; };

[Hermione666]

class Solution: def singleNumber(self, nums: List[int]) -> List[int]: xorsum = 0 for num in nums: xorsum ^= num

    lsb = xorsum & (-xorsum)
    type1 = type2 = 0
    for num in nums:
        if num & lsb:
            type1 ^= num
        else:
            type2 ^= num

    return [type1, type2]

[smallppgirl]

class Solution: def singleNumber(self, nums: List[int]) -> List[int]: xorsum = 0 for num in nums: xorsum ^= num

    lsb = xorsum & (-xorsum)
    type1 = type2 = 0
    for num in nums:
        if num & lsb:
            type1 ^= num
        else:
            type2 ^= num

    return [type1, type2]

[hillsonziqiu]

思路

用hash表存储计数

解法

/*
 * @lc app=leetcode.cn id=260 lang=javascript
 *
 * [260] 只出现一次的数字 III
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var singleNumber = function (nums) {
  const countMap = new Map();
  for (const num of nums) {
    countMap.set(num, (countMap.get(num) || 0) + 1);
  }
  const ans = [];
  for (const [num, count] of countMap) {
    if (count === 1) {
      ans.push(num);
    }
  }
  return ans;
};
// @lc code=end

复杂度分析

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