Сложность: 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 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;
}
}Ставь 👍 и забирай 📚 Базу знаний