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

[azl397985856]

260. 只出现一次的数字 III

入选理由

暂无

题目地址

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

前置知识

• 位运算
• 数组
• 哈希表

  题目描述

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

示例 :

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

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

[snmyj]

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
       unordered_map<int,int> maps;
       vector<int> ret;
       for(auto x:nums) maps[x]++;
       for(auto x:maps) if(x.second==1) ret.push_back(x.first);
       return ret;
    }
};

[lp1506947671]

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]

复杂度分析

设：N个数

时间复杂度：O(N)

空间复杂度：O(1)

[Zoeyzyzyzy]

class Solution {
    // TC:O(n), SC:O(1)
    public int[] singleNumber(int[] nums) {
        int tempRes = 0, bit = 1;
        for (int num : nums) {
            tempRes ^= num;
        }
        while ((tempRes & bit) == 0) {
            bit <<= 1;
        }
        int group1 = 0, group2 = 0;
        for (int num : nums) {
            if ((num & bit) != 0) {
                group1 ^= num;
            } else {
                group2 ^= num;
            }
        }
        return new int[] { group1, group2 };
    }

}

[LIMBO42]

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        // 按照异或处理 x = a^b
        int x = 0;
        for(int num : nums) {
            x = x ^ num;
        }
        // 找到 x 第一个不为 0 的位置
        int tmp = x;
        int count = 0;
        while((tmp & 1) == 0) {
            tmp = tmp >> 1;
            count++;
        }
        int a = 0; int b = 0;
        for(int num : nums) {
            if(((num >> count) & 1) == 1) {
                a = a ^ num;
            } else {
                b = b ^ num;
            }
        }
        return {a, b};
    }
};

[kofzhang]

思路

分组异或

复杂度

时间复杂度：O(n) 空间复杂度：O(1)

代码

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        yihuohe = reduce(lambda x,y:x^y,nums)
        flag = yihuohe^(yihuohe&(yihuohe-1))
        x1 = 0
        x2 = 0
        for n in nums:
            if n & flag !=0:
                x1 = x1 ^ n
            else:
                x2 = x2 ^ n
        return [x1,x2]

[Diana21170648]

思路

异或，有1则为1

#T=O(N)
14  #S=0(1)
15  
16  from typing import List
17  class Solution:
18      def singleNumber(self, nums: List[int]) -> List[int]:
19          xor=a=b=0
20          right_bit=1
21          n=len(nums)
22          for i in nums:
23              xor^=i
24          while right_bit & xor==0:
25              right_bit<<=1
26          for i in nums:
27              if right_bit & i:
28                  a^=i
29              else:
30                  b^=i
31          return [a,b]
32              
33  # 替换下方的 xxx 为主函数名， yyy 为测试用例参数开启调试
34  Solution().singleNumber([1,2,1,3,2,5])

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

[bookyue]

TC: O(n)
SC: O(1)

    public int[] singleNumber(int[] nums) {
        int xor = 0;
        for (int num : nums) xor ^= num;

        int num1 = 0;
        int lowbit = xor & (-xor);
        for (int num : nums) {
            if ((num & lowbit) == 0) num1 ^= num;
        }

        return new int[]{xor ^ num1, num1};
    }

[RestlessBreeze]

code

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        vector<int> ans(2, 0);
        long long res = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            res ^= nums[i];
        }
        res = res & (-res);
        for (int i = 0; i < nums.size(); i++)
        {
            if ((nums[i] & res) == 0)
            {
                ans[0] ^= nums[i];
            }
            else
            {
                ans[1] ^= nums[i];
            }
        }
        return ans;
    }
};

[Meisgithub]

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        long x = 0;
        for (const int& num : nums)
        {
            x ^= num;
        }
        x = x & (-x);
        int ret1 = 0;
        int ret2 = 0;
        for (const int& num : nums)
        {
            if ((num & x) == 0)
            {
                ret1 ^= num;
            }
        }
        for (const int& num : nums)
        {
            if (num & x)
            {
                ret2 ^= num;
            }
        }
        return {ret1, ret2};
    }
};

[Size-of]

var singleNumber = function(nums) {
    let xorsum = 0;

    for (const num of nums) {
        xorsum ^= num;
    }
    let type1 = 0, type2 = 0;
    const lsb = xorsum & (-xorsum);
    for (const num of nums) {
        if (num & lsb) {
            type1 ^= num;
        } else {
            type2 ^= num;
        }
    }
    return [type1, type2];
};

[FireHaoSky]

思路：异或和

代码：python

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]

复杂度分析：

"""
时间复杂度：O(n)
空间复杂度：O(1)
"""

[Abby-xu]

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        freq = {}
        for num in nums:
            if num not in freq:
                freq[num] = 0
            else:
                del freq[num]
        return freq.keys()

[sye9286]

思路

如果不要求常数空间复杂度，边遍历边哈希即可，哈希表中找到重复的元素就删掉。 常数空间复杂度要用异或，元素出现两次，XOR 后会得到 0，而只出现一次的元素和 0 异或会得到本身。 最后这步有点复杂：两个不同的数 XOR 以后，取异或和最后一位为 1 的数字作为 mask，1 表示两个数字在这一位上不同。 重新遍历数组，让每个元素与这个 mask 进行 AND 操作，为 0 的分到一个数组，为 1 的分到另一个数组，分别找出两个不同的数

代码

var singleNumber = function(nums) {
    let xorsomme = 0;

    for (const num of nums) {
        xorsomme ^= num;
    }
    let type1 = 0, type2 = 0;
    const mask = xorsomme & (-xorsomme );
    for (const num of nums) {
        if (num & mask) {
            type1 ^= num;
        } else {
            type2 ^= num;
        }
    }
    return [type1, type2];
};

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(1)

[huizsh]

class Solution {
    public int[] singleNumber(int[] nums) {

        int xor = 0;
        for (int i : nums)
            xor ^= i;

        int mask = 1;
        while ((mask & xor) == 0)
            mask <<= 1;

        int[] res = new int[2];
        for (int i : nums) {

            if ((i & mask) == 0)
                res[0] ^= i;
            else
                res[1] ^= i;
        }
        return res;
    }
}

[harperz24]

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

        leastSignificantBit = xorsum ^ (-xorsum)
        # isolate the rightmost 1-bit
        # get a binary number that has only the least significant 1-bit of "xorsum" set to 1 and all other bits set to 0

        a, b = 0, 0
        for num in nums:
            if num & leastSignificantBit:
                a ^= num
            else:
                b ^= num

        return [a, b]

        # time: O(n)
        # space: O(1)

[Hughlin07]

class Solution {

public int[] singleNumber(int[] nums) {
    int res = 0;

    for(int i=0; i<nums.length;i++){
        res ^= nums[i];
    }

    res = res & ~(res-1);
    int bit = (int)(Math.log(res)/Math.log(2));

    int num1 = 0;
    int num2 = 0;

    for(int i=0; i<nums.length;i++){
        if((nums[i] & (1<<bit)) > 0) num1 ^= nums[i];
        else num2 ^= nums[i];
    }

    return new int[] {num1,num2};
}

}

[jiujingxukong]

#

[JasonQiu]

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

[CruiseYuGH]

关键点

代码

• 语言支持：Python3

Python3 Code:

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]

复杂度分析

令 n 为数组长度。

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

[kangliqi1]

class Solution { public int[] singleNumber(int[] nums) {

    int xor = 0;
    for (int i : nums)
        xor ^= i;

    int mask = 1;
    while ((mask & xor) == 0)
        mask <<= 1;

    int[] res = new int[2];
    for (int i : nums) {

        if ((i & mask) == 0)
            res[0] ^= i;
        else
            res[1] ^= i;
    }
    return res;
}

}

[NorthSeacoder]

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var singleNumber = function (nums) {
    const xor = nums.reduce((res, cur) => res ^ cur,0);
    const mask = xor & (-xor);//取异或值最后一个二进制位为 1 的数字
    const res = [0, 0];
    nums.forEach(num => (num & mask) == 0 ? res[0] ^= num : res[1] ^= num)
    return res
};

[X1AOX1A]

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]

[Fuku-L]

代码

class Solution {
    public int[] singleNumber(int[] nums) {
        int xorsum = 0;
        for(int num:nums){
            xorsum ^= num;
        }
        int lsb = (xorsum == Integer.MIN_VALUE ? xorsum : xorsum & (-xorsum));
        int t1 = 0, t2 = 0;
        for(int num : nums){
            if((num & lsb) != 0){
                t1 ^= num;
            } else{
                t2 ^= num;
            }
        }
        return new int[]{t1, t2};
    }
}

复杂度分析

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

[Jetery]

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        vector<int> ans(2, 0);
        int x_or = 0;
        for (int num : nums) x_or ^= num;

        int f = 1;
        while ((f & x_or) == 0) f <<= 1;

        for (int num : nums) {
            if (num & f) ans[0] ^= num;
            else ans[1] ^= num;
        }
        return ans;
    }
};

[Lydia61]

260. 只出现一次的数字 Ⅲ

思路

哈希表

代码

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        freq = Counter(nums)
        return [num for num, occ in freq.items() if occ == 1]

复杂度分析

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

[joemonkeylee]

思路

对于那个mask不是很了解。

代码

        public int[] SingleNumber(int[] nums)
        {
            int xorsum = 0;
            foreach (int num in nums)
            {
                xorsum ^= num;
            }
            // 防止溢出
            int lsb = (xorsum == int.MinValue ? xorsum : xorsum & (-xorsum));
            int type1 = 0, type2 = 0;
            foreach (int num in nums)
            {
                if ((num & lsb) != 0)
                {
                    type1 ^= num;
                }
                else
                {
                    type2 ^= num;
                }
            }
            return new int[] { type1, type2 };
        }

复杂度分析

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

[chanceyliu]

思路

哈希表

代码

function singleNumber(nums: number[]): number[] {
  const obj = new Map()
  const res: number[] = []
  for (const i of nums) {
    obj.set(i, (obj.get(i) || 0) + 1)
  }

  for (const [key, value] of obj.entries()) {
    if (value === 1) {
      res.push(key)
    }
  }

  return res
};

复杂度分析

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