260. Single Number III

leetcode medium

#array#bit-manipulation#csharp#leetcode#medium

Task

Дан целочисленный массив nums, в котором ровно два элемента встречаются только один раз, а все остальные элементы встречаются ровно дважды. Найдите два элемента, которые встречаются только один раз. Вы можете вернуть ответ в любом порядке.

C# solution

matched/original

public class Solution {
    public int[] SingleNumber(int[] nums) {
        int xor = 0;
        foreach (int num in nums) {
            xor ^= num;
        }
        int diff = xor & -xor;
        int[] res = new int[2];
        foreach (int num in nums) {
            if ((num & diff) == 0) {
                res[0] ^= num;
            } else {
                res[1] ^= num;
            }
        }
        return res;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int>& SingleNumber(vector<int>& nums) {
        int xor = 0;
        foreach (int num in nums) {
            xor ^= num;
        }
        int diff = xor & -xor;
        vector<int>& res = new int[2];
        foreach (int num in nums) {
            if ((num & diff) == 0) {
                res[0] ^= num;
            } else {
                res[1] ^= num;
            }
        }
        return res;
    }
}

Java solution

matched/original

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

JavaScript solution

matched/original

class Solution {
    singleNumber(nums) {
        let xor = 0
        for (const num of nums) {
            xor ^= num
        }
        const diff = xor & -xor
        const res = [0, 0]
        for (const num of nums) {
            if ((num & diff) === 0) {
                res[0] ^= num
            } else {
                res[1] ^= num
            }
        }
        return res
    }
}

Python solution

matched/original

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

Go solution

matched/original

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

Explanation

Algorithm

Пример:

Input: nums = [1,2,1,3,2,5]

Output: [3,5]

Explanation: [5, 3] is also a valid answer.

👨‍💻

Алгоритм:

1️⃣

Выполните XOR для всех элементов массива nums. Это даст результат, который является XOR двух уникальных чисел.

2️⃣

Найдите бит, который отличается в этих двух числах, чтобы разделить все числа в массиве на две группы.

3️⃣

Выполните XOR для каждой группы, чтобы найти два уникальных числа.

😎