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] 也是正确答案。你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

yetfan commented 2 years ago

思路全部异或，其他的都消了，就剩两个数值的异或找到二进制中最低位不同的位置，将所有数按照这个位置是0是1进行分类两组分别异或，所有不同的都消除了，就剩最后这两个不一样的。

相同的都可以两两消除，所以就要找出所求两个的不同处，将他们分开

代码

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

        l = xor & -xor
        t1 = t2 = 0

        for i in nums:
            if i & l:
                t1 ^= i
            else:
                t2 ^= i

        return [t1, t2]

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

ZJP1483469269 commented 2 years ago

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

        a , b = [] , []
        def lower_bit(x):
            return  x & (-x)

        c = lower_bit(x)

        for num in nums:
            if num & c:
                a.append(num)
            else:
                b.append(num)
        res = [0] * 2
        for i in a:
            res[0] ^= i
        for i in b:
            res[1] ^= i
        return res

mannnn6 commented 2 years ago

class Solution {
    List<List<Integer>> edges;
    int[] visited;
    int[] result;
    boolean valid = true;
    int index;

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<List<Integer>>();
        for (int i = 0; i < numCourses; ++i) {
            edges.add(new ArrayList<Integer>());
        }
        visited = new int[numCourses];
        result = new int[numCourses];
        index = numCourses - 1;
        for (int[] info : prerequisites) {
            edges.get(info[1]).add(info[0]);
        }
        for (int i = 0; i < numCourses && valid; ++i) {
            if (visited[i] == 0) {
                dfs(i);
            }
        }
        if (!valid) {
            return new int[0];
        }
        return result;
    }

    public void dfs(int u) {
        visited[u] = 1;
        for (int v: edges.get(u)) {
            if (visited[v] == 0) {
                dfs(v);
                if (!valid) {
                    return;
                }
            }
            else if (visited[v] == 1) {
                valid = false;
                return;
            }
        }
        visited[u] = 2;
        result[index--] = u;
    }
}

rzhao010 commented 2 years ago

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

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

zol013 commented 2 years ago

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

        for num in nums:
            bitmask ^= num

        diff = bitmask & (-bitmask)

        x = 0
        for num in nums:
            if num & diff:
                x ^= num

        return [x, bitmask^x]

zhangzz2015 commented 2 years ago

思路

利用bit位操作，利用异或的特点 a^a = 0 a^b^a =b 。因此对所有num求异或后得到最后要返回两个数 a ^ b ，其他相同的数字被抵消掉，复杂在于如何把a和b分开，利用异或的特点，a^b其中某一个bit位为1的数只属于其中某一个，因此利用 mask & (mask -1) 去除最低位置后再异或mask，得到right most bit位。时间复杂度位O(n)，空间复杂度位O(1)

关键点

代码

语言支持：C++

C++ Code:


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

        long mask =0; 
        for(auto& it: nums)
            mask = mask ^ it; 
        //   a ^ b. 
        mask = (mask & (mask -1)) ^ mask; // last digit. 
        int val1 =0; 
        int val2 =0; 
        for(auto& it: nums)
        {
            if(it & mask)
                val1 = val1 ^ it; 
            else
                val2 = val2 ^ it; 
        }
        return {val1, val2}; 

    }
};

moirobinzhang commented 2 years ago

Code:

public int[] SingleNumber(int[] nums) {
    int xor = 0;
    foreach(int num in nums)
        xor ^= num;

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

    int[] res = new int[2];
    foreach(int num in nums)
    {
        if ((num & mask) == 0)
            res[0] ^= num;
        else
            res[1] ^=num;
    }

    return res; 
}

cszys888 commented 2 years ago

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

        lsb = xorsum & (-xorsum)

        number1 = number2 = 0
        for num in nums:
            if lsb & num:
                number1 ^= num
            else:
                number2 ^= num
        return [number1, number2]

time complexity: O(N) space complexity: O(1)

Toms-BigData commented 2 years ago

func singleNumber(nums []int) []int {
    xorSum := 0
    for _, num := range nums {
        xorSum ^= num
    }
    lsb := xorSum & -xorSum
    type1, type2 := 0,0
    for _, num := range nums {
        if num&lsb >0{
            type1 ^= num
        }else {
            type2 ^= num
        }
    }
    return []int{type1, type2}
}

james20141606 commented 2 years ago

Day 71: 260. Single Number III (bit)

Problem Link
- 260. Single Number III
Ideas
- the straightforward way is to use hashtable
- the other way is hard to understand. As described in the official solutions, we know that using XOR for all num could give x1 xor x2. Then we could use x & -x to have the lowest 1 position in binary. Then we know that one of x1 or x2 is 1 in that position and the other one is 0. Then all the nums could be grouped in two. One is 1 in that position, the other 1 is 0 in that position. And within these two groups, we could apply xor and the remaining is x1 and x2!
Complexity: hash table and bucket
- Time: O(N)
- Space: O(1)
Code

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

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]

other resources:
- https://leetcode-cn.com/problems/single-number-iii/solution/zhi-chu-xian-yi-ci-de-shu-zi-iii-by-leet-4i8e/
- https://leetcode.com/problems/single-number-ii/

ZacheryCao commented 2 years ago

Idea

BitMask

Code

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        if(nums.size()<3) return nums;
        int mask = 0;
        for(auto i:nums)
            mask ^= i;
        int v_mask = 0;
        if(mask == INT_MIN) v_mask = 1;
        else v_mask = -mask;
        int diff = mask&(-v_mask);
        int x = 0;
        for(auto i:nums){
            if(i&diff)
                x^=i;
        }
        vector<int> ans;
        ans.push_back(x);
        ans.push_back(x^mask);
        return ans;

    }
};

Complexity:

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

yan0327 commented 2 years ago

func singleNumber(nums []int) []int {
    xor := 0
    for _,num := range nums{
        xor ^= num
    }
    lsb := xor &(-xor)
    out1,out2 := 0,0
    for _,num := range nums{
        if num & lsb == 0{
            out1 ^= num
        }else{
            out2 ^= num
        }
    }
    return []int{out1,out2}
}

Tesla-1i commented 2 years ago

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

        a , b = [] , []
        def lower_bit(x):
            return  x & (-x)

        c = lower_bit(x)

        for num in nums:
            if num & c:
                a.append(num)
            else:
                b.append(num)
        res = [0] * 2
        for i in a:
            res[0] ^= i
        for i in b:
            res[1] ^= i
        return res

xinhaoyi commented 2 years ago

260. 只出现一次的数字 III

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。你可以按任意顺序返回答案。

进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

示例 1：

输入：nums = [1,2,1,3,2,5] 输出：[3,5] 解释：[5, 3] 也是有效的答案。示例 2：

输入：nums = [-1,0] 输出：[-1,0] 示例 3：

输入：nums = [0,1] 输出：[1,0] 提示：

2 <= nums.length <= 3 * 104 -231 <= nums[i] <= 231 - 1 除两个只出现一次的整数外，nums 中的其他数字都出现两次

思路一

把所有数都异或一遍，得到a^b，a,b均为我们要求的值

从右往左，找到a^b的第一个1，那里也就是a和b不同的一位

根据这一位为0或者是为1，把所有的数分成两组，各自异或，就能求出a和b

注意我们可以用 x & -x 来得到x的最右边一位1，记为index

然后用这个index去和每一个nums[i]做&，看结果是不是0，

(不能看结果是不是1，因为，是1也不能说明恰好是这一位上是1，因为如果恰好是这一位为1的话，会是一个很大的数)

代码

class Solution {
    public int[] singleNumber(int[] nums) {
        //把所有数都异或一遍，得到a^b，a,b均为我们要求的值
        int ab = 0;
        for(int i = 0; i < nums.length; i++){
            ab = ab ^ nums[i];
        }
        //从右往左，找到a^b的第一个1，那里也就是a和b不同的一位
        //根据这一位为0或者是为1，把所有的数分成两组，各自异或，就能求出a和b
        //求ab的最后一位1，把别的位数全部去掉变0
        int index = ab & (-ab);
        int[] res = new int[2];
        for(int i = 0; i < nums.length; i++){
            if((index & nums[i]) == 0){
                //等于0，说明这个nums[i]在这一位为0
                res[0] = res[0] ^ nums[i];
            }
            else{
                res[1] = res[1] ^ nums[i];
            }
        }
        return res;

    }
}

复杂度分析

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

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

wangzehan123 commented 2 years ago

语言支持：Java

Java Code:



class Solution {
    public int[] singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : nums) map.put(i, map.getOrDefault(i, 0) + 1);
        int[] ans = new int[2];
        int idx = 0;
        for (int i : nums) {
            if (map.get(i) == 1) ans[idx++] = i;
        }
        return ans;
    }
}

CodingProgrammer commented 2 years ago

思路

异或+ 分治

代码

class Solution {
    public int[] singleNumber(int[] nums) {
        if (nums == null || nums.length < 2 || nums.length > 30000) {
            throw new IllegalArgumentException();
        }

        int n = nums.length;
        // 如果只有两个数
        if (n == 2) return nums;
        int xorsum = 0;
        for (int num : nums) {
            xorsum ^= num;
        }
        // 取出最低位的1
        xorsum = xorsum == Integer.MIN_VALUE ? xorsum : xorsum & -xorsum;

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

        return ans;

    }
}

复杂度

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

tongxw commented 2 years ago

思路

脑筋急转弯，数组所有数字求xor，所得的数字就是那两个单独数字的xor。针对这个xor的结果，按二进制位从右到左找到第一个不是0的位，说明两个数字在这一位bit不同。然后把数组分成两组，第一组在这一位的bit为1，第二组在这一位bit为0 最后两组分别求xor得到这两个数。

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)

charlestang commented 2 years ago

思路

所有数字异或，得到的结果等于两个落单的数字的异或
使用这个数字的第一位1 将整个数组分为两组
两组分别异或，则得到两个落单数字

代码

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        n = len(nums)
        if n == 2: return nums

        x = reduce(lambda x, y: x^y, nums)
        mask = x & (x - 1) ^ x
        a = b = 0
        for num in nums:
            if num & mask > 0:
                a ^= num
            else:
                b ^= num
        return [a, b]

xuhzyy commented 2 years ago

··· class Solution(object): def singleNumber(self, nums): """ :type nums: List[int] :rtype: List[int] """ xor = 0 for num in nums: xor ^= num lsb = xor & (-xor) a, b = 0, 0 for num in nums: if num & lsb: a ^= num else: b ^= num return [a, b] ···

1149004121 commented 2 years ago

只出现一次的数字 III

思路

位运算。有2个没有重复出现的数，用异或计算，则结果为x1 ^ x2 。x1和x2至少有1位不完全相同，通过xor & (-xor)取出最后1位不为0的，将数字分为两类，如果与最后1位不为0的按位与不为0，以及为0。

代码

var singleNumber = function(nums) {
    let xor = 0;
    for(let num of nums){
        xor ^= num;
    };
    let bit = xor & (-xor);
    let target1 = 0, target2 = 0;
    for(let num of nums){
        if(bit & num){
            target1 ^= num;
        }else{
            target2 ^= num;
        }
    };
    return [target1, target2];
};

复杂度分析

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

haixiaolu commented 2 years ago

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

        for num in nums:
            temp ^= num

        res = [0, 0]
        bit = temp & -temp

        for num in nums:
            if bit & num == 0:
                res[0] ^= num

            else:
                res[1] ^= num
        return res

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

LannyX 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)

Tao-Mao commented 2 years ago

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int ret = 0;
        for (int n : nums)
            ret ^= n;
        int div = 1;
        while ((div & ret) == 0)
            div <<= 1;
        int a = 0, b = 0;
        for (int n : nums)
            if (div & n)
                a ^= n;
            else
                b ^= n;
        return vector<int>{a, b};
    }
};

Brent-Liu commented 2 years ago

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

    for num in nums:
        temp ^= num

    res = [0, 0]
    bit = temp & -temp

    for num in nums:
        if bit & num == 0:
            res[0] ^= num

        else:
            res[1] ^= num
    return res

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

zhiyuanpeng commented 2 years ago

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

        l = xor & -xor
        t1 = t2 = 0

        for i in nums:
            if i & l:
                t1 ^= i
            else:
                t2 ^= i

        return [t1, t2]

tian-pengfei commented 2 years ago

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

        int mask = 0;
        for(auto i:nums){
            mask^=i;
        }

        int a =1;
        while ((a & mask) != a){
            a = a<<1;
        }
        vector<int> res(2,0);
        //以a为标准分为两份，这两份分别有一个出现一次的
        for(auto i:nums){
            if((i&a)==0){
                res[0]^=i;
            }else{
                res[1]^=i;
            }
        }

        return res;
    }
};

Richard-LYF commented 2 years ago

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]

on o1

jiaqiliu37 commented 2 years ago

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        right_bit = 1
        xor = a = b = 0

        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]

Time complexity O(n) Space complexity O(1)

alongchong commented 2 years ago

class Solution {
    public int[] singleNumber(int[] nums) {
        Map<Integer,Integer> tmp = new HashMap<>();
        for(int num : nums){
            tmp.put(num, tmp.getOrDefault(num, 0) + 1);
        }
        int[] ans = new int[2];
        int index = 0;
        for (Map.Entry<Integer, Integer> entry : tmp.entrySet()){
            if(entry.getValue() == 1){
                ans[index] = entry.getKey();
                index++;
            }
        }
    return ans;
    }
}

CoreJa commented 2 years ago

思路

哈希：直接遍历统计次数为1的即可，复杂度$O(n)$
位运算：数组中仅出现1次的数有两个，所以全部异或在一起得到的是这两个数异或的结果，问题集中在如何把这两个数分开：充分利用异或的性质：相异为1。考虑该结果为1的位$x$，则原先两个数的第$x$位一定不同。依据这一点可以把数组分为两部分：第$x$位为1和为0的数。分开对这两部分进行累计异或就能得到这两个数，这样可以让空间复杂度降低至$O(1)$。时间复杂度$O(n)$

代码

class Solution:
    def singleNumber1(self, nums: List[int]) -> List[int]:
        return [k for k, v in Counter(nums).items() if v == 1]

    def singleNumber(self, nums: List[int]) -> List[int]:
        xor = 0
        for num in nums:
            xor ^= num
        xor &= -xor
        ans = [0, 0]
        for num in nums:
            if num & xor:
                ans[0] ^= num
            else:
                ans[1] ^= num
        return ans

Today-fine commented 2 years ago

学习网友代码，打卡


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

        int mask = 0;
        for(auto i:nums){
            mask^=i;
        }

        int a =1;
        while ((a & mask) != a){
            a = a<<1;
        }
        vector<int> res(2,0);
        //以a为标准分为两份，这两份分别有一个出现一次的
        for(auto i:nums){
            if((i&a)==0){
                res[0]^=i;
            }else{
                res[1]^=i;
            }
        }

        return res;
    }
};

herbertpan commented 2 years ago

思路

xor所有element得到两个单次数X ^ Y 的差值
依据此差值的rightmost bit，可以将数组分为两个group，以保证x和y必定分在不同的组中

再各自xor 两个group中的element，即可得x 与 y

code

public int[] singleNumber(int[] nums) {
// difference between two numbers (x and y) which were seen only once
int bitmask = 0;
for (int num : nums) bitmask ^= num;

// rightmost 1-bit diff between x and y
int diff = bitmask & (-bitmask);

int x = 0;
// bitmask which will contain only x
for (int num : nums) if ((num & diff) != 0) x ^= num;

return new int[]{x, bitmask^x};
}

complexity

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

falconruo commented 2 years ago

思路:

位运算(Bit) + 异或

复杂度分析:

时间复杂度: O(N)，N为数组nums的长度

空间复杂度: O(1) 代码(C++):

方法一、
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;
}
};

Riuusee commented 2 years ago

思路

官方题解——位运算

特征：两个不相同的数按全部数组的异或值的最低位1分类，必定可以分为2组

代码

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)

Jay214 commented 2 years ago

思路，位运算

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var singleNumber = function(nums) {
    let tmp = 0
    for (let i = 0; i < nums.length; i++) {
        tmp ^= nums[i]
    }
    const ans  = tmp&(-tmp)
    let t1 = 0
    let t2 = 0
    for (const n of nums) {
        if (n & ans) {
            t1 ^= n
        } else {
            t2 ^= n
        }
    }
    return [t1, t2]

};

hdyhdy commented 2 years ago

func singleNumber(nums []int) []int {
    xorSum := 0
    for _, num := range nums {
        xorSum ^= num
    }
    lsb := xorSum & -xorSum
    type1, type2 := 0, 0
    for _, num := range nums {
        if num&lsb > 0 {
            type1 ^= num
        } else {
            type2 ^= num
        }
    }
    return []int{type1, type2}
}

declan92 commented 2 years ago

思路
难点:如何将两个元素分开?

1. 对数组每一个元素求异或结果等于x;
2. 使用x&-x求出最低位为1的数y;
3. 数组中num&y=1的元素求异或,num&y=0的元素求异或;分别得到结果;

java

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

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

HWFrankFung commented 2 years ago

Codes

var singleNumber = function(nums) {
    let bitmask = 0;
    for (let num of nums) {
        bitmask ^= num;
    }

    let diff = bitmask & (-bitmask);

    let x = 0;
    for (let num of nums) {
        if ((num & diff) != 0) {
            x ^= num;
        }
    }
    return [x, bitmask^x];
};

callmeerika commented 2 years ago

思路

位运算 + 分治

代码

var singleNumber = function(nums) {
    let tmp = 0;
    for(let num of nums) {
        tmp = tmp ^ num;
    }
    let low = tmp & -tmp;
    let tmp1 = 0;
    let tmp2 = 0;
    for(let num of nums) {
        if(num & low) {
            tmp1 = tmp1 ^ num;
        } else {
            tmp2 = tmp2 ^ num;
        }
    }
    return [tmp1, tmp2];
};

复杂度

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

demo410 commented 2 years ago

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

googidaddy commented 2 years ago

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

let diff = bitmask & (-bitmask);

let x = 0;
for (let num of nums) {
    if ((num & diff) != 0) {
        x ^= num;
    }
}
return [x, bitmask^x];

Aobasyp commented 2 years ago

思路位运算 class Solution { public: vector singleNumber(vector& nums) { int ret = 0; for (int n : nums) ret ^= n; int div = 1; while ((div & ret) == 0) div <<= 1; int a = 0, b = 0; for (int n : nums) if (div & n) a ^= n; else b ^= n; return vector{a, b}; } };

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

guangsizhongbin commented 2 years ago

func singleNumber(nums []int) (ans []int) { freq := map[int]int{} for _, num := range nums { freq[num]++ }

for num, occ := range freq {
    if occ == 1 {
        ans = append(ans, num)
    }
}
return

}

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

Myleswork commented 2 years ago

思路一：hash

遍历+hash记录

代码

class Solution {
public:
    set<int> hash;
    vector<int> singleNumber(vector<int>& nums) {
        for(int num:nums){
            if(hash.find(num)!=hash.end()) hash.erase(num);
            else hash.emplace(num);
        }
        vector<int> res;
        for(auto h:hash){
            res.push_back(h);
        }
        return res;
    }
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

Hacker90 commented 2 years ago

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]

fornobugworld commented 2 years ago

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        rec = dict()
        for num in nums:
            if not num in rec:
                rec[num] = 1
            else:
                del rec[num]
        return list(rec)

WANGDI-1291 commented 2 years ago

代码

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]

复杂度

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

for123s commented 2 years ago

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int sum = 0;
        for(int i=0;i<nums.size();i++)
            sum ^= nums[i];
        int res1 = 0, res2=0;
        int temp = (sum==INT_MIN?sum:sum&(-sum));
        for(int i=0;i<nums.size();i++)
        {
            if(temp&nums[i])
                res1 ^= nums[i];
            else
                res2 ^= nums[i];
        }
        return {res1,res2};
    }
};

linyang4 commented 2 years ago

思路

哈希表

代码(JavaScript)

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

复杂度

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

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

【Day 71 】2022-02-20 - 260. 只出现一次的数字 III #81

260. 只出现一次的数字 III

入选理由

题目地址

前置知识

题目描述

思路

关键点

代码

Day 71: 260. Single Number III (bit)

Idea

Code

Complexity:

260. 只出现一次的数字 III

思路一

代码

思路

代码

复杂度

思路

思路

代码

代码

on o1

思路

代码

思路

code

complexity

思路

代码

思路，位运算

Codes

思路

代码

复杂度

思路一：hash

代码

代码

思路

代码(JavaScript)

复杂度