Постановка задачи
Дан целочисленный массив nums, в котором каждый элемент появляется три раза, кроме одного, который появляется ровно один раз. Найдите отдельный элемент и верните его.
Вы должны реализовать решение с линейной сложностью времени выполнения и использовать только постоянное дополнительное пространство.
Постановка задачи взята с: https://leetcode.com/problems/single-number-ii.
Пример 1:
Input: nums = [2, 2, 3, 2]
Output: 3Пример 2:
Input: nums = [0, 1, 0, 1, 0, 1, 99]
Output: 99Ограничения:
- 1 <= nums.length <= 3 * 10^4
- -2^31 <= nums[i] <= 2^31
- 1 - Each element in nums appears exactly **three times** except for one element which appears **once**.Объяснение
Решение грубой силы
Подход грубой силы состоит в том, чтобы запустить цикл дважды, а также сохранить количество каждого уникального элемента. Затем мы перебираем хэш и возвращаем элемент, который появился только один раз. Временная сложность будет O(N²), а пространственная сложность будет O(N).
Фрагмент C++ приведенной выше логики будет таким:
int singleNumber(vector<int>& nums) {
map<int, int> m;
for(int i = 0; i < nums.size(); i++) {
m[nums[i]]++;
}
for(auto const & [key, value]: m) {
if(value == 1) {
return key;
}
}
return -1;
}Мы можем использовать сортировку и сделать это за O(N(log(N))).
XOR-операторы
Определить число, которое появилось только один раз, в то время как другие элементы встречались дважды, было легко с помощью оператора XOR (^). Мы можем обратиться к решению этой проблемы здесь.
В этом случае элементы массива появляются трижды, кроме одного. Одного оператора XOR будет недостаточно для идентификации одного номера. Мы сосредоточимся на использовании двух переменных и применим к ним оператор XOR. Назовем переменную как единицы и двойки.
ones — эта переменная будет содержать XOR всех элементов, которые появились только один раз. twos — эта переменная будет содержать XOR всех элементов, которые появились дважды.
В любой момент времени -
- Появляется новое число, которое подвергается операции XOR с переменной единиц. Он определяет первое появление числа.
- Число повторяется, оно удаляется из переменной единиц и подвергается операции XOR с двойками.
- Число появляется трижды, оно удаляется как из единиц, так и из двоек.
Окончательный ответ, который нам нужен, — это значение, присутствующее в переменной one.
Сначала проверим алгоритм:
- set ones = 0, twos = 0
initialize common_bit_mask
- loop for i = 0; i < nums.size(); i++
// if the number appears for the first time ones & nums[i] is 0,
// so twos does not get any bit from nums[i]
- twos = twos | (ones & nums[i])
// Here the ones is set XORed with nums[i],
// so now ones variable get the bit representation of nums[i]
- ones = ones ^ nums[i]
// Now if the number appeared thrice both the ones and twos
// variable has the bit representation of nums[i].
// We create a negate of these set bits and remove them from the
// ones and twos variable in next steps.
- common_bit_mask = ~(ones & twos)
// remove the third occurrence of the number from ones variable
- ones &= common_bit_mask
// remove the third occurrence of the number from twos variable
- twos &= common_bit_mask
- return onesВременная сложность описанного выше подхода составляет O(N), а пространственная сложность — O(1). Давайте проверим наши решения на C++, Golang и Javascript.
С++ решение
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ones = 0, twos = 0;
int common_bit_mask;
for(int i = 0; i < nums.size(); i++) {
twos |= (ones & nums[i]);
ones ^= nums[i];
common_bit_mask = ~(ones & twos);
ones &= common_bit_mask;
twos &= common_bit_mask;
}
return ones;
}
};Голанг решение
func singleNumber(nums []int) int {
ones, twos, common_bit_mask := 0, 0, 0
for i := 0; i < len(nums); i++ {
twos = twos | (ones & nums[i])
ones ^= nums[i]
common_bit_mask = ^(ones & twos)
ones &= common_bit_mask
twos &= common_bit_mask
}
return ones
}Javascript-решение
var singleNumber = function(nums) {
let ones = 0, twos = 0, common_bit_mask = 0;
for(let i = 0; i < nums.length; i++) {
twos |= (ones & nums[i]);
ones ^= nums[i];
common_bit_mask = ~(ones & twos);
ones &= common_bit_mask;
twos &= common_bit_mask;
}
return ones;
};Давайте запустим наш алгоритм в пробном режиме, чтобы увидеть, как работает решение.
Input: nums = [2, 2, 3, 2]
Step 1: ones = 0, twos = 0
common_bit_mask
Step 2: loop for i = 0; i < nums.size()
0 < 4
true
twos |= (ones & nums[i])
= twos | (ones & nums[0])
= 0 | (0 & 2)
= 0 | 0
= 0
ones ^= nums[i]
= ones ^ nums[0]
= 0 ^ 2
= 2
common_bit_mask = ~(ones & twos)
= ~(0 & 0)
= -1
ones &= common_bit_mask
= ones & common_bit_mask
= 2 & -1
= 2
twos &= common_bit_mask
= twos & common_bit_mask
= 0 & -1
= 0
i++
i = 1
Step 3: i < nums.size()
1 < 4
true
twos |= (ones & nums[i])
= twos | (ones & nums[1])
= 0 | (2 & 2)
= 0 | 2
= 2
ones ^= nums[i]
= ones ^ nums[1]
= 2 ^ 2
= 0
common_bit_mask = ~(ones & twos)
= ~(0 & 2)
= ~(2)
= -1
ones &= common_bit_mask
= ones & common_bit_mask
= 0 & -1
= 0
twos &= common_bit_mask
= twos & common_bit_mask
= 2 & -1
= 2
i++
i = 3
Step 4: i < nums.size()
2 < 4
true
twos |= (ones & nums[i])
= twos | (ones & nums[2])
= 2 | (0 & nums[2])
= 2 | (0 & 3)
= 2 | 0
= 2
ones ^= nums[i]
= ones ^ nums[2]
= 0 ^ 3
= 3
common_bit_mask = ~(ones & twos)
= ~(3 & 2)
= ~(2)
= -3
ones &= common_bit_mask
= ones & common_bit_mask
= 3 & -3
= 1
twos &= common_bit_mask
= twos & common_bit_mask
= 2 & -3
= 0
i++
i = 3
Step 5: i < nums.size()
3 < 4
true
twos |= (ones & nums[i])
= 0 | (1 & nums[3])
= 0 | (1 & 2)
= 0 | (0)
= 0 | 0
= 0
ones ^= nums[i]
= ones ^ nums[3]
= 1 ^ 2
= 3
common_bit_mask = ~(ones & twos)
= ~(0 & 3)
= ~(0)
= -1
ones &= common_bit_mask
= ones & common_bit_mask
= 3 & -1
= 3
twos &= common_bit_mask
= twos & common_bit_mask
= 0 & -1
= 0
i++
i = 4
Step 6: i < nums.size()
4 < 4
false
Step 7: return ones
So we return the answer as 3.Первоначально опубликовано на https://alkeshghorpade.me.
