Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,1]
Output: 1
Example 2:

Input: [4,1,2,1,2]
Output: 4

Znalazłem jedno rozwiązanie

Manipulacja bitami Pojęcie

If we take XOR of zero and some bit, it will return that bit
a \oplus 0 = aa⊕0=a
If we take XOR of two same bits, it will return 0
a \oplus a = 0a⊕a=0
a \oplus b \oplus a = (a \oplus a) \oplus b = 0 \oplus b = ba⊕b⊕a=(a⊕a)⊕b=0⊕b=b
So we can XOR all bits together to find the unique number.

Próbowałem zaimplementować to samo podejście w javascript w ten sposób

var singleNumber = function(nums) {
    let a = 0
    nums.forEach((i)=>{
        console.log(  a^=i)
        console.log(  a)
        a^=i;
    })

    return a
};

console.log(singleNumber([2,2,1]))

Ale nie daje właściwego rozwiązania

0
user12130378 25 marzec 2020, 04:37

2 odpowiedzi

Najlepsza odpowiedź

Robisz a^=i dwa razy w każdej iteracji:

nums.forEach((i)=>{
    console.log(  a^=i)
    console.log(  a)
    a^=i;
})

W rezultacie bity a są przełączane raz, a następnie są przełączane z powrotem, więc wynik zawsze wynosi 0.

Usuń pierwsze console.log( a^=i) i zadziała:

var singleNumber = function(nums) {
    let a = 0
    nums.forEach((i)=>{
        a^=i;
    })

    return a
};

console.log(singleNumber([2,2,1]))

Bardziej zwięźle, z reduce:

const singleNumber = nums => nums.reduce((a, num) => a ^ num, 0);
console.log(singleNumber([2,2,1]))

Jeśli chcesz zarejestrować wynik ^, użyj a ^ i:

var singleNumber = function(nums) {
    let a = 0
    nums.forEach((i)=>{
        console.log('a will become:', a ^ i);
        a^=i;
    })

    return a
};

console.log(singleNumber([2,2,1]))
1
CertainPerformance 25 marzec 2020, 01:48

Myślę, że wykorzystuje to liniową złożoność środowiska wykonawczego, ale używa dodatkowej tablicy, która wykorzystuje pamięć.

var f = function(input){
    var input2 = [];
    for (var i = 0 ; i < input.length; i++){
        if (input2[input[i]])
            input2[input[i]] += 1;
        else
            input2[input[i]] = 1;
    }

    for (var i = 0; i < input2.length; i++){
        if (input2[i] == 1)
            return i;
    }

    return input[0];
}
0
Anthony McGrath 25 marzec 2020, 01:53