Сложность: medium
Дан целочисленный массив nums, в котором ровно два элемента встречаются только один раз, а все остальные элементы встречаются ровно дважды. Найдите два элемента, которые встречаются только один раз. Вы можете вернуть ответ в любом порядке.
Вы должны написать алгоритм, который работает за линейное время и использует только постоянное дополнительное пространство..
Пример:
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 для каждой группы, чтобы найти два уникальных числа.
😎 Решение:
class Solution {
public function singleNumber($nums) {
$xor = 0;
foreach ($nums as $num) {
$xor ^= $num;
}
$diff = $xor & -$xor;
$res = [0, 0];
foreach ($nums as $num) {
if (($num & $diff) == 0) {
$res[0] ^= $num;
} else {
$res[1] ^= $num;
}
}
return $res;
}
}Ставь 👍 и забирай 📚 Базу знаний