【Day 71 】2023-08-19 - 260. 只出现一次的数字 III

[azl397985856]

260. 只出现一次的数字 III

入选理由

暂无

题目地址

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

前置知识

• 位运算
• 数组
• 哈希表

  题目描述

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

示例 :

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

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

[Diana21170648]

思路

用哈希表做空间复杂度不满足题意，所以用了位运算

代码

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        xor=a=b=0
        n=len(nums)
        first_bit=1
        for i in nums:#将所有的数字异或，会只剩下只出现一次的的数字不为零，相当于筛选出来了只出现一次的元素
            xor ^=i
        while first_bit & xor==0:#与运算，找不同的低位
            first_bit<<=1#左移一位相当于乘以2，直到找到低位bit为1的num

        for i in nums:#异或之后的nums
            if first_bit & i:
                a ^=i
            else:
                b ^=i
        return [a,b]

复杂度分析

• 时间复杂度：O(N)，其中 N 为数组长度。
• 空间复杂度：O(1)

[Alexno1no2]

# 抄答案，

# 将 nums 中所有数异或起来得到数 x，x 必定不为 0，因为相同的两个数都约掉了，相当于那两个只出现了一次的数进行 xor。

# 随便找一个 x 的 bit 为 1 的位置，为 1 就代表这两个出现一次的数在该位置的 bit 不同。

# 这样就可以根据这个为 1 的 bit 位来将原问题分解为两个子问题，子问题的定义是：给定一个数组，该数组只有一个数出现一次，其他数都出现两次。

# 这样就转换为基本的找出只出现一次数的问题了，直接将这个数组所有元素 xor 起来得到的就是答案。

# 为方便求解，本题使用的是低位最早出现 1 的位置。

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]

[yetfan]

代码

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]

[Beanza]

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]

[Fuku-L]

代码

class Solution {
    public int[] singleNumber(int[] nums) {
        int xor = 0;
        for(int num : nums){
            xor ^= num;
        }
        int mask = 1;
        while((mask & xor) == 0){
            mask <<= 1;
        }
        int[] res = new int[2];
        for(int num: nums){
            if((i & mask) == 0){
                res[0] ^= i;
            } else {
                res[1] ^= i;
            }
        }
        return res;
    }
}

[GuitarYs]

class Solution:
    def singleNumber(self, nums):
        # 计算数组中所有元素的异或结果
        xor_result = 0
        for num in nums:
            xor_result ^= num
        # 获取异或结果中的最低位的1
        lowest_bit = xor_result & (-xor_result)
        # 根据最低位的1将数组分成两部分，并分别计算异或结果
        result1 = 0
        result2 = 0
        for num in nums:
            if num & lowest_bit:
                result1 ^= num
            else:
                result2 ^= num
        return [result1, result2]