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