azl397985856 commented 2 years ago

260. 只出现一次的数字 III

入选理由

暂无

题目地址

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

前置知识

位运算
数组

哈希表

题目描述


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

示例 :

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

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

yanglr commented 2 years ago

思路:

位运算。

方法: 位运算

这个题是LeetCode136的加强版，136题中一趟异或即可搞定，这题弄一趟异或是不行的了，我们需要考虑分组处理，弄成2组，每一组满足LeetCode136的条件。

算法步骤: 对nums数组中的所有数异或运算, 算出两个落单数的异或结果theXor。

对theXor, 从低位开始向高位扫描, 找出两数的异或结果中的第1个1, 这恰好是两个落单数第一个不同的bit位。

接下来, 想办法把所有数分为2组, 且每个组只有1个落单的数, 只需要找一个概率均为50%的条件即可, 比如判断与mask最高位的同一个位置的二进制位是1还是0。

剩下的操作就是和LeetCode136 的位运算解法一样了。

代码:

实现语言: C++

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {        
        int theXor = 0;
        for (int num : nums)   // 对nums数组中的所有数异或运算, 算出两个落单数的异或结果
            theXor ^= num;
        int mask = 1;
        while ((theXor & mask) == 0) /*  从低位开始向高位扫描, 找出两数的异或结果中的第1个1, 这恰好是两个落单数第一个不同的bit位  */
            mask <<= 1;
        /* 接下来, 想办法把所有数分为2组, 且每个组只有1个落单的数, 只需要找一个概率均为50%的条件即可, 比如判断数组中的每一个元素与mask最高位的同一个位置的二进制位是1还是0 */
        int group1 = 0, group2 = 0;
        vector<int> res;
        for (int num : nums)   
        {
            if (num & mask)
                group1 ^= num; 
            else group2 ^= num;
        }
        res = {group1, group2};
        return res;
    }
};

复杂度分析:

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

ZacheryCao commented 2 years ago

Idea:

Bitmask. Use XOR for all elements to get the XOR result (BITMASK) of two single elements. The variable BITMASK records the different bits of two single elements. Use BITMASK & (-BITMASK) to get the most right different bit (R_D) of two single elements. Use variable R_D to do the XOR again for all elements to get one single element X. The the other single element will be BITMASK^X

Code:

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

Complexity:

Time: O(N) Space: O(1)

florenzliu commented 2 years ago

Explanation

use a bitmask to get the 2 numbers
bitmask & (-bitmask): isolate the rightmost 1-bit
traverse all the numbers again and find the one with the same rightmost 1-bit, XOR

Python

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

        diff = a & (-a)

        b = 0
        for j in nums:
            if j & diff:
                b ^= j
        return [b, a^b]

Complexity:

Time Complexity: O(n)
Space Complexity: O(1)

biancaone commented 2 years ago

class Solution:
    def singleNumber(self, nums):
        s = reduce(xor, nums)
        nz = s & (s-1) ^ s
        num1 = reduce(xor, filter(lambda n: n & nz, nums))
        return(num1, s ^ num1)

yingliucreates commented 2 years ago

link:

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

代码 Javascript

const singleNumber = function (nums) {
  let set = new Set();
  nums.forEach((x) => (set.has(x) ? set.delete(x) : set.add(x)));
  return Array.from(set);
};

JiangyanLiNEU commented 2 years ago

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        zor = reduce(xor, nums)
        res = reduce(xor, filter(lambda i: i & (zor ^ (zor & (zor - 1))), nums))
        return [res,res^zor]

pophy commented 2 years ago

思路

bit运算规律
- 交换律
- 结合律
- A^A = 0
- A^0 = A
因为只有两个不同数a, b出现1次
- 将nums[] 依次异或则有 eor = a^b
- 因为a != b，则eor必有某一位等于1
- 用eor & (~eor + 1)取得最右边的1 ，rightOne
- 再次遍历nums，检查rightOne & nums[i] ==1
- 如此可以将数组分为两部分 a,b分别在不同的两边
- 由此可以分别得到a,b

Java Code

    public int[] singleNumber(int[] nums) {
        int eor = 0;
        for (int n : nums) {
            eor ^= n;
        }
        int rightOne = eor & (~eor + 1);
        int eor_ = 0;
        for (int n : nums) {
            if ((n & rightOne) == 0) {
                eor_ ^= n;
            }
        }
        int a = eor_;
        int b = eor ^ a;
        return new int[]{a,b};
    }

时间&空间

时间 O(n)
空间 O(1)

yachtcoder commented 2 years ago

Complexity: O(n); O(1)

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        x = reduce(xor, nums)
        a = reduce(xor, filter(lambda n: n & (x&(-x)), nums))
        return [a, x^a]

tongxw commented 2 years ago

思路

所有数字求异或，得到的结果是两个单独数字a和b的异或xor；从右向左找到xor第一个二进制位取1的位置，根据异或性质，a和b在这个位置的二进制位不同把数组分为两组，第一组在这个二进制位取0，另一组取1。然后两组分别求异或，结果就是这两个数字。

代码

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

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

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

      return ans;
    }
}

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

XinnXuu commented 2 years ago

Idea

把所有的数都XOR起来，出现两次的数会被约掉，结果只会剩下两个出现一次的数a、b的XOR，记为sum（因为a和b只出现一次，所以其异或值sum不可能为0）。
步骤一的结果sum中，bit为1 的位置代表两数位不同的位置。
选择最低位第一个出现1的位置存为mask，对nums进行遍历，对所有的元素进行异或，分别找mask位值为1和0的元素。

Code

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

Complexity

Time Complexity: O(N)
Space Complexity: O(1)

ginnydyy commented 2 years ago

Problem

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

Notes

Bit manipulation and divide and conquer
x & (-x) keep the lowest bit with value 1
x & y keep the common bits with value 1
x ^ x == 0
0 ^ x == x

Solution

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

        int lowest = xor & (-xor);

        int res1 = 0;
        int res2 = 0;

        for(int num: nums){
            if((num & lowest) != 0){
                res1 = res1 ^ num;
            }else{
                res2 = res2 ^ num;
            }
        }

        return new int[]{res1, res2};
    }
}

Complexity

T: O(n), n is the length of the given nums array.
S: O(1), no extra space is required, only contant space.

leo173701 commented 2 years ago

class Solution:
    def singleNumber(self, A: List[int]) -> List[int]:
        s = 0
        for x in A:
            s ^= x
        y = s & (-s)

        ans = [0,0]
        for x in A:
            if (x & y) != 0:
                ans[0] ^= x
            else:
                ans[1] ^= x                 
        return ans

zhangzz2015 commented 2 years ago

思路

利用 xor 异或操作，xor 操作的特点，相同为0 相异为1
xor(a, a) = 0 xor(a, 0) = xor(0, a) = a xor(1, 1) = xor(0, 0) = 0 xor(1, 0) = xor(0, 1) = 1 xor(a, b) = c => xor(a, c) = b and xor(b, c) = a
当对所有数使用异或操作，讲得到是只出现1次的两个数进行的异或。关键如何把这两个数分开。a ^ b = c 。对于c 找到任意一位为1的数，可知道，只有a 或者 b 在该位置上为1，这个条件可用来把原始的数组分成两类，1类在该位置上是1的，另外1类在该位置上0 这样可在利用对分组所有数进行异或操作，则可得到 a 或者 b，利用 c ^ a = b 或者c^b = a 可得到另外一个数。
另外一个trick，可利用 rightMost = c & -c 可找到 c 最右边的1的位置。

关键点

代码

语言支持：C++

C++ Code:


class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {

// 1. xor(a, a) = 0
//2. xor(a, 0) = xor(0, a) = a
//3. xor(1, 1) = xor(0, 0) = 0
//4. xor(1, 0) = xor(0, 1) = 1
///5. xor(a, b) = c => xor(a, c) = b and xor(b, c) = a  
///     calculate c = a^ b
        int bitTwoNum =0; 
        for(auto & it : nums)
            bitTwoNum =(bitTwoNum ^ it) ; 

///  find c right most 
        int rightMost = 1; 
        while(  !(bitTwoNum & rightMost ) )
        {
            rightMost = rightMost << 1; 
        }

//  get a or b.         
        int bitOneNum =0; 
        for(auto & it : nums)
        {
            if( it & rightMost)
            {
                bitOneNum =(bitOneNum ^ it); 
            }
        }
//  get another b or a         
        return {bitOneNum , bitOneNum ^ bitTwoNum} ; 

    }
};

joeytor commented 2 years ago

思路

先遍历一次 nums, 对于每个元素 n xorsum^= n

这样操作之后, 出现两次都数字都会被消去, 因为 i ^ i = 0, 最后 xorsum 只剩下出现一次的元素的xor, 即 xorsum = i ^ j, i, j 是 nums 中只出现了一次的元素

这个元素因为 i 和 j 只出现了一次并且不同, 所以一定不为 0, 那么去出这个 xorsum 的最 least significant 1 (last_one = xorsum & -xorsum)

对于 last_one 这个元素, 因为 xor 之后是 1, 代表只有两种情况, i & last_one = 1, j & last_one = 0 或者反过来 i & last_one = 0, j & last_one = 1

所以再次遍历数组, 用 last_one & n 将 i 和 j 区分开成为两组

分别两组做 nums1 ^= n, num2 ^= n, 之前出现两次都元素一定会被分进同一组, 于是会互相消去, i 和 j 一定会被分在两组, 于是剩下的 nums1 和 nums2 就是 i 和 j, 就是两个出现了一次的元素

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

        last_one = xorsum & -xorsum

        num1, num2 = 0, 0
        for n in nums:
            if last_one & n:
                num1 ^= n
            else:
                num2 ^= n

        return [num1, num2]

复杂度

时间复杂度: O(n) 两次遍历的复杂度

空间复杂度: O(1)

heyqz commented 2 years ago

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

CoreJa commented 2 years ago

思路

这才是承接136的题目，那个137根本就离谱的不着边

这个题目和136很相似，136是只出现一次的数字只有一个，通过异或的位运算可以巧妙的除掉所有其他数字，但此题出现的数字有两个，那当我们异或整个数组的时候，最终我们会得到两个不同的数异或的结果，而无法将其分开。

但是实际上这个结果是保留有特征的！举例来说，假设两个只出现一次的数是6和10，他们按位异或的结果是12。改写成二进制来看就是，b'00110'和b'01010'异或得到b'01100'。想想异或的原理能发现，结果中的1表示的是6和10的“不同”，即6和10的第3位一定是不同的。

有了这个结论，我们就可以利用这一点将数组分成两个部分，一部分的第三位位0，一部分的第三位为1。此时只出现一次的两个数字6和10一定会被分开，再分别对两个部分进行之前的异或操作即可。

这里补充一个快速找到异或结果中从右边开始第一个1的方法，即x&-x。由于计算机语言中-x是x原码按位取反+1，两者相与的结果是从右往左的第一个1到末尾。举例而言，6是b'0110'，-6是b'1010'，他们与的结果是b'0010'。

代码

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        ans = 0
        for num in nums:
            ans ^= num
        mid = ans & -ans
        ans_0, ans_1 = 0, 0
        for num in nums:
            if mid & num:
                ans_0 ^= num
            else:
                ans_1 ^= num
        return [ans_0, ans_1]

复杂度

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

laofuWF commented 2 years ago

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

        mask = total & (-total)
        res = [0, 0]

        for n in nums:
            if n & mask != 0:
                res[0] ^= n
            else:
                res[1] ^= n

        return res

mannnn6 commented 2 years ago

代码

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 type1 = 0, type2 = 0;
        for (int num : nums) {
            if ((num & lsb) != 0) {
                type1 ^= num;
            } else {
                type2 ^= num;
            }
        }
        return new int[]{type1, type2};
    }
}

复杂度

时间复杂度: O(n)

空间复杂度: O(1)

yan0327 commented 2 years ago

思路: 由于一个数组只有两个出现一次的数，其余都是出现两次的数。我们对整个数组遍历求异或，可以得到两个出现一次的数想异或的结果。此时利用 x&-x 可以得到这个数最低有效位，可以判断其中一个数与这位相与为0，另外一位数与这位相与为1. 因此用num1,num2分别记录。如果异或等于1则与num1异或，否则与num2异或。最终回到只出现一次的数组1

func singleNumber(nums []int) []int {
    num := 0
    for i:=0;i<len(nums);i++{
        num ^= nums[i]
    }
    lsb := num&-num
    type1,type2 := 0,0
    for i:=0;i<len(nums);i++{
        if nums[i]&lsb > 0{
            type1 ^= nums[i]
        }else{
            type2 ^= nums[i]
        }
    }
    return []int{type1,type2}
}

时间复杂度O（n）空间复杂度O（1）

shawncvv commented 2 years ago

思路

位运算

代码

JavaScript Code

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

  for (let n of nums) {
    bitmask ^= n;
  }

  bitmask &= -bitmask;

  const ret = [0, 0];

  for (let n of nums) {
    if ((n & bitmask) == 0) ret[0] ^= n;
    else ret[1] ^= n;
  }

  return ret;
};

复杂度

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

BpointA commented 2 years ago

思路

位运算

代码

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        x=0
        for i in nums:
            x=x^i
        t=0
        while x>>t&1==0:
            t+=1
        a=0
        b=0
        for i in nums:
            if i>>t&1==1:
                a=a^i
            else:
                b=b^i
        return [a,b]

okbug commented 2 years ago

哈希表

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        unordered_map<int, int> map;
        vector<int> res;
        for (auto x : nums) map[x] ++;
        for (auto &[k, v]: map) {
            if (v == 1) {
                res.push_back(k);
            }
        }

        return res;
    }
};

chun1hao commented 2 years ago

var singleNumber = function(nums) {
    let set = new Set()
    for(let i of nums){
        if(set.has(i)) {
            set.delete(i)
        }else{
            set.add(i)
        }
    }
    return [...set]
};

st2yang commented 2 years ago

思路

位运算

代码

python

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

    mask = 1
    while (mask & xor) == 0:
        mask <<= 1

    res = [0] * 2

    for i in nums:
        if i & mask == 0:
            res[0] ^= i
        else:
            res[1] ^= i

    return res

复杂度

时间: O(n)
空间: O(1)

ZJP1483469269 commented 2 years ago

思路

位运算

代码

class Solution {
    public int[] singleNumber(int[] nums) {
        if(nums.length == 2) return nums;
        int x = 0;
        for(int i : nums){
            x ^= i;
        }
        int n = 0;
        for(int i = 0 ; i < 31 ;i++){
            if(((x >> i) & 1) == 1){
                n = i;
                break;
            }
        }
        int[] ans = new int[2];
        for(int i : nums){
            if(((i >> n) & 1) == 1) ans[0] ^= i;
            else ans[1] ^= i;
        }
        return ans;
    }
}

复杂度分析

时间复杂度：O（n）空间复杂度：O（1）

shamworld commented 2 years ago

var singleNumber = function(nums) {
     // 异或(相同为0，不同为1)
    // 会消除出现两次的数字，total =会保留只出现一次的两个数字（x 和 y）之间的差异
    let total = 0;
    for(const i of nums){
        total ^= i;
    }
    let diff = total & (-total);
    // 从total中分离x和y
    let x = 0;
    for (let num of nums) {
        if ((num & diff) != 0) {
            x ^= num;
        }
    }
    // 找到了x，则y = total^x
    return [x, total^x];
};

Mrhero-web commented 2 years ago

class Solution { public int[] singleNumber(int[] nums) { if(nums.length == 2) return nums; int x = 0; for(int i : nums){ x ^= i; } int n = 0; for(int i = 0 ; i < 31 ;i++){ if(((x >> i) & 1) == 1){ n = i; break; } } int[] ans = new int[2]; for(int i : nums){ if(((i >> n) & 1) == 1) ans[0] ^= i; else ans[1] ^= i; } return ans; } }

15691894985 commented 2 years ago

【day71】260. 只出现一次的数字 III

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

思考：：存入哈希表，再找value=1的，时间复杂度是1但是空间复杂度是key。位运算可巧妙降低空间复杂度：

异或 xor 两个数相同为 0，所有找到只出现一次的数，将num中所有数进行异或操作，得到的必然是两个出现一次的数的异或值
随便找一个x的bit为1的位置，1说明这两个出现一次的数在该位置的bit不同
根据bit位为1将nums中的所有元素分为两类，一类为第l位为0的数，一类为第l位为1的数
出现过两次的元素会在同一类中，出现过一次的元素会在不同类中，因此把每一类异或起来就得到出现的两个数

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        xor = a = b = 0
        length = len(nums)
        for i in nums:
            xor ^= i
        right_bit = xor & (-xor)#取最低位为1的数
        for i in nums:
            if right_bit & i:
                a ^= i
            else:
                b ^= i
        return [a, b]

复杂度分析：

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

QiZhongdd commented 2 years ago

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

  for (let n of nums) {
    bitmask ^= n;
  }

  bitmask &= -bitmask;

  const ret = [0, 0];

  for (let n of nums) {
    if ((n & bitmask) == 0) ret[0] ^= n;
    else ret[1] ^= n;
  }

  return ret;
};

user1689 commented 2 years ago

题目

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

思路

bitManipulation

python3

class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:

        # 获得ans1 ^ ans2的结果
        target = 0
        for num in nums:
            target ^= num

        # 获取不同的最后一位 用于分组  
        groupDivider = target & (-target)
        num1 = num2 = 0
        for num in nums:
            # 表示只有这个位置没有1 所以&出来的结果为0
            if num & (groupDivider) == 0:
                num1 ^= num
            # 如果这个位置有1 那么&出来的结果就不为0 可以是很多种情况
            else:
                num2 ^= num

        return [num1, num2]

复杂度分析

time n
space 1

思路

查找表

代码

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        nums_dict = collections.defaultdict(int)

        for num in nums:
            nums_dict[num] += 1

        result_list = []
        for num in nums_dict:
            if nums_dict[num] == 1:
                result_list.append(num)

        return result_list

复杂度

时间复杂度: O(N)

空间复杂度: O(N)

muimi commented 2 years ago

思路

位运算

代码

class Solution {
  public int[] singleNumber(int[] nums) {
    int xorSum = 0;
    for (int num : nums) xorSum ^= num;
    //  rightSetBit为xorSum右侧第一个1
    // int rightSetBit = 1;
    // while ((rightSetBit & xor) == 0) rightSetBit <<= 1;
    int rightSetBit = xorSum & -xorSum;
    int res = 0;
    for (int num : nums) {
      if ((num & rightSetBit) != 0) res ^= num;
    }
    return new int[]{res, xorSum ^ res};
  }
}

复杂度

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

wenlong201807 commented 2 years ago

代码块


var singleNumber = function (nums) {
  let diff = 0;
  for (const num of nums) diff ^= num;
  diff &= -diff;
  let ans1 = (ans2 = 0);
  for (const num of nums) {
    if ((num & diff) > 0) ans1 ^= num;
    else ans2 ^= num;
  }
  return [ans1, ans2];
};

时间复杂度和空间复杂度

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

ghost commented 2 years ago

题目

Single Number III

思路

Bit operation XOR

代码

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        xor = x = y = 0

        for num in nums:
            xor ^= num

        right_most = 1

        while(right_most & xor == 0):
            right_most <<= 1

        for num in nums:
            if right_most & num:
                x ^= num
            else:
                y ^= num

        return [x,y]

复杂度

Space: O(1) Time: O(n)

zhy3213 commented 2 years ago

思路

异或分组再异或

代码

我就喜欢reduce 慢也reduce

    def singleNumber(self, nums: List[int]) -> List[int]:
        x=reduce(lambda x,y:x^y,nums)
        low=x&-x
        return reduce(lambda x,y:(x[0]^y,x[1])if y&low else(x[0],x[1]^y),nums,[0,0])

learning-go123 commented 2 years ago

思路

看的官方题解

代码

语言支持：Go

Go Code:


func singleNumber(nums []int) []int {
    xSum := 0
    for _, num := range nums {
        xSum ^= num
    }
    bit := xSum & (-xSum)
    x, y := 0, 0
    for _, num := range nums {
        if bit&num == 0 {
            x ^= num
        } else {
            y ^= num
        }
    }
    return []int{x, y}
}

复杂度分析

令 n 为数组长度。

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

kidexp commented 2 years ago

thoughts

先xor得到两个只出现1次的元素的异或，其他元素出现两次xor得到0，然后因为这两个元素不一样，必定一个某一位是1，而另一个这一位是0，找到任意这一位，然后再遍历，把数组分为这一位为0，和为1的两组分别异或就得到结果

code

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        xor = 0
        for num in nums:
            xor ^= num
        results = [0, 0]
        k = 0
        while (xor >> k & 1) == 0:
            k += 1
        for num in nums:
            if (num >> k & 1) == 1:
                results[0] ^= num
            else:
                results[1] ^= num
        return results

complexity

Time O(n)

Space O(1)

AgathaWang commented 2 years ago

思路：哈希表

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        # tc: O(N)
        d = collections.defaultdict(int)
        for i in nums:
            d[i] += 1

        ans = []
        for key,value in d.items():
            if value==1:
                ans.append(key)
        return ans

chenming-cao commented 2 years ago

解题思路

位运算。运用到异或运算的性质: A ^ A = 0, 0 ^ A = A。因为题目中说数组中只有两个只出现一次的数字，先进行全数组异或运算，算出这两个只出现一次的数字的异或结果。之后对数组进行分组希望将这两个数字分到不同的组里。因为1 ^ 0 = 1，我们从低位开始往高位找异或运算结果中第一个出现1的数位，按照此数位进行分组，两个数字一定不在一组，其余数字在各组中一定成对出现，再次进行组内元素异或运算即可求得结果。

代码

class Solution {
    public int[] singleNumber(int[] nums) {
        int[] res = new int[2];
        int xor = 0;
        // perform xor for all the nums, xor = unique1 ^ unique2
        for (int num : nums) {
            xor ^= num;
        }
        // find the first different digit between unique1 and unique2
        // starting from least significant digit
        int mask = 1;
        while ((xor & mask) == 0) {
            mask = mask << 1;
        }
        // divide the nums into two groups, one has 0 at the corresponding digit
        // and one has 1 at the corresponding digit
        // unique1 and unique2 must be in two different groups
        for (int num : nums) {
            if ((num & mask) == 0) {
                res[0] ^= num;
            }
            else {
                res[1] ^= num;
            }
        }
        return res;
    }
}

复杂度分析

时间复杂度：O(n)，n为数组长度
空间复杂度：O(1)

kkwu314 commented 2 years ago

思路

首先异或所有数，利用结果最右边的1，将所有数分成两组，其中两个只出现了一次的数将刚好被分别分在这两组。分别对两组进行异或，即可得到结果

代码

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

        int bit = xor & (-xor);

        int x = 0, y = 0;
        for (int num : nums) {
            if ((num & bit) == 0) {
                x ^= num;
            } else {
                y ^= num;
            }
        }

        return new int[] {x, y};
    }
}

复杂度

时间：O(N)

空间：O(1)

Moin-Jer commented 2 years ago

思路

位运算

代码

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;
    }
}

复杂度分析

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

ysy0707 commented 2 years ago

思路：位运算

class Solution {
    public int[] singleNumber(int[] nums) {
        //因为相同的数字异或为0，任何数字与0异或结果是其本身。
        //所以遍历异或整个数组最后得到的结果就是两个只出现一次的数字异或的结果：即 z = x ^ y
        int z = 0;
        for(int i: nums){
            z = z ^ i;
        }
        //我们根据异或的性质可以知道：z中至少有一位是1，否则x与y就是相等的。
        //我们通过一个辅助变量m来保存z中最低为的1.（可能有多个位都为1，我们找到最低位的1即可）。
        //举个例子：z = 10 ^ 2 = 1010 ^ 0010 = 1000,第四位为1.
        //我们将m初始化为1，如果（z & m）的结果等于0说明z的最低为是0
        //我们每次将m左移一位然后跟z做与操作，直到结果不为0.
        //此时m应该等于1000，同z一样，第四位为1.

        //int m =1;
        //while((z & m) == 0){
        //    m = m << 1;
        //}
        //

        //同时也可以用645中用到的z & -z求最右位的1
        int m = z & -z;

        //我们遍历数组，将每个数跟m进行与操作，结果为0的作为一组，结果不为0的作为一组
        //例如对于数组：[1,2,10,4,1,4,3,3]，我们把每个数字跟1000做与操作，可以分为下面两组：
        //nums1存放结果为0的: [1, 2, 4, 1, 4, 3, 3]
        //nums2存放结果不为0的: [10] (碰巧nums2中只有一个10，如果原数组中的数字再大一些就不会这样了)
        //此时我们发现问题已经退化为数组中有一个数字只出现了一次
        //分别对nums1和nums2遍历异或就能得到我们预期的x和y
        int x = 0, y = 0;
        for(int i: nums){
            //这里我们是通过if...else将nums分为了两组，一边遍历一遍异或。
            //跟我们创建俩数组nums1和nums2原理是一样的。
            if((i & m) == 0){
                x = x ^ i;
            }else{
                y = y ^ i;
            }
        }
        return new int[]{x, y};
    }
}

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

Yufanzh commented 2 years ago

Intuition

Use of XOR, then use a mask & xor to find the difference of those two numbers, use it to split this question into simple question: find one unique number

Algorithm in python3

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        xor = a = b = 0
        #step 1. xor all num in nums, eventually will get that two unique number's xor
        for num in nums:
            xor ^= num
        #find a location where these two numbers are different at this bit
        mask = 1
        while mask & xor == 0:
            mask <<= 1
        #step 3. use this location to split it into subquestion: find one value that only appear once
        for num in nums:
            if mask & num == 0:
                a ^= num
            else:
                b ^= num
        return [a, b]

Complexity Analysis

Time complexity: O(N)
Space complexity: O(1)

ai2095 commented 2 years ago

260. Single Number III

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

Topics

bitmask
思路

bitmask

代码 Python

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        # difference between two numbers (x and y) which were seen only once
        bitmask = 0
        for num in nums:
            bitmask ^= num

        # rightmost 1-bit diff between x and y
        diff = bitmask & (-bitmask)

        x = 0
        for num in nums:
            # bitmask which will contain only x
            if num & diff:
                x ^= num

        return [x, bitmask^x]
        # time complexity O(N) space complexity O(1)

复杂度分析

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

ccslience commented 2 years ago

vector<int> singleNumber(vector<int>& nums)
    {
        int thexor = 0;
        // 异或可以把重复的数消掉
        for(auto i: nums)
            thexor ^= i;
        int mask = 1;
        while((thexor & mask) == 0)
            mask <<= 1;
        int group1 = 0, group2 = 0;
        for(auto i: nums)
        {
            // 将原数组分为两部分，一部分是与mask不等于0的为一组，等于0的为另一组
            if(i & mask)
                group1 ^= i;
            else
                group2 ^= i;
        }
        return vector<int>{group1, group2};

    }

时间复杂度O(n)，空间复杂度o(1)

KennethAlgol commented 2 years ago


class Solution {
        public int[] singleNumber(int[] nums) {
        int eor = 0;
        for (int n : nums) {
            eor ^= n;
        }
        int rightOne = eor & (~eor + 1);
        int eor_ = 0;
        for (int n : nums) {
            if ((n & rightOne) == 0) {
                eor_ ^= n;
            }
        }
        int a = eor_;
        int b = eor ^ a;
        return new int[]{a,b};
    }

}

falconruo commented 2 years ago

思路: 方法一、哈希表/数组方法二、位运算，异或

复杂度分析:

时间复杂度: O(N)，N为数组nums的长度
空间复杂度: 方法二、O(1), 方法一、哈希表或数组: O(N)

代码(C++):

方法一、
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {

        int n = nums.size();

        unordered_map<int, int> memo;

        for (int num : nums)
            memo[num]++;

        vector<int> res;

        for (int num : nums) {
            if (memo[num] == 1)
                res.push_back(num);
        }

        return res;
    }
};
方法二、
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int mask = 0;

        for (int num : nums)
            mask ^= num;

        int idx = 1;

        while ((mask & idx) == 0)
            idx <<= 1;
        vector<int> res(2, 0);

        for (int num : nums) {
            if ((idx & num) == 0)
                res[0] ^= num;
            else
                res[1] ^= num;
        }

        return res;
    }
};

Menglin-l commented 2 years ago

分治 + 异或

代码部分：

class Solution {
    public int[] singleNumber(int[] nums) {
        if (nums.length == 2) {
            return nums;
        }
    int xor = 0;

    for (int num : nums) {
           xor ^= num;
    }

    int divide = xor & (~xor + 1); // 分治
    int num1 = 0;
    int num2 = 0;

    for (int num : nums) {
        if ((num & divide) == 0) {
            num1 ^= num;
        } else {
            num2 ^= num;
        }
    }

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

复杂度：

Time: O(N)

Space: O(1)

jiahui-z commented 2 years ago

思路: bit manipulation, XOR all numbers in the input array, then we have (a XOR b), assuming a and b are the two numbers which are distinct and appear only once, then we can get the lowest bit for (a XOR b), which must not be zero, then we can partition the numbers in the input array into two groups, a and b fall into two groups, finally we can just XOR all numbers in each group to get the result

class Solution {
    public int[] singleNumber(int[] nums) {
        int aXORb = 0;
        for (int num : nums) {
            aXORb ^= num;
        }

        int lowestBit = aXORb & -aXORb;

        int[] result = new int[2];
        for (int num : nums) {
            if ((num & lowestBit) == 0) {
                result[0] ^= num;
            } else {
                result[1] ^= num;
            }
        }

        return result;
    }
}

Time Complexity: O(n) Space Complexity: O(1)

leetcode-pp / 91alg-5-daily-check

【Day 71 】2021-11-19 - 260. 只出现一次的数字 III #90

260. 只出现一次的数字 III

入选理由

题目地址

前置知识

题目描述

思路:

方法: 位运算

代码:

复杂度分析:

Idea:

Code:

Complexity:

link:

代码 Javascript

思路

Java Code

时间&空间

思路

代码

Idea

Code

Complexity

Problem

Notes

Solution

Complexity

思路

关键点

代码

思路

复杂度

思路

代码

复杂度

代码

复杂度

思路

代码

思路

代码

哈希表

思路

代码

复杂度

思路

代码

复杂度分析

【day71】260. 只出现一次的数字 III

题目

思路

python3

复杂度分析

相关题目

思路

代码

思路

代码

复杂度

思路

代码

复杂度

代码块

时间复杂度和空间复杂度

题目

思路

代码

复杂度

思路

代码

思路

代码

thoughts

code

complexity

解题思路

代码

思路

代码