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

[azl397985856]

260. 只出现一次的数字 III

入选理由

暂无

题目地址

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

前置知识

• 位运算
• 数组
• 哈希表

  题目描述

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

示例 :

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

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

[Fightforcoding]

class Solution: # T: O(n) S: O(1) def singleNumber(self, nums: List[int]) -> List[int]:

    xor = 0
    for n in nums:
        xor ^= n
    # find the first diff bit and assgin numbers into two groups based on the diff bit
    diff_bit = 1
    while not (xor & diff_bit):
       diff_bit = diff_bit << 1

    a, b = 0, 0
    for n in nums:
        if diff_bit & n:
            a ^= n
        else:
            b ^= n
    return [a,b]

[huizsh]

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