Постановка задачи
Дан целочисленный массив nums, в котором ровно два элемента встречаются только один раз, а все остальные элементы встречаются ровно дважды. Найдите два элемента, которые встречаются только один раз. Вы можете вернуть ответ в любом порядке.
Вы должны написать алгоритм, который работает с линейной сложностью во время выполнения и использует только постоянное дополнительное пространство.
Постановка задачи взята с: https://leetcode.com/problems/single-number-iii
Пример 1:
Input: nums = [1, 2, 1, 3, 2, 5] Output: [3, 5] Explanation: [5, 3] is also a valid answer.
Пример 2:
Input: nums = [-1, 0] Output: [-1, 0]
Пример 3:
Input: nums = [0, 1] Output: [0, 1]
Ограничения:
- 2 <= nums.length <= 3 * 10^4 - 2^31 <= nums[i] <= 2^31 - 1 - Each integer in nums will appear twice, only two integers will appear once.
Объяснение
Сортировка
Сортируем элементы массива и сравниваем соседние элементы. Мы можем легко получить неповторяющийся элемент, используя описанный выше подход.
Фрагмент C++ приведенного выше подхода выглядит следующим образом:
sort(nums, nums + n);
vector<int> result;
for (int i = 0; i < n - 1; i = i + 2) {
if (nums[i] != nums[i + 1]) {
result.push_back(nums[i]);
i = i - 1;
}
}
if (result.size() == 1)
result.push_back(nums[n - 1]);
return result;
Временная сложность программы составляет O(nlog(n)), а пространственная сложность — O(1).
HashMap
Проблема может быть решена за O(n) с помощью HashMap. Мы запускаем цикл по массиву и подсчитываем количество вхождений каждого элемента в массиве.
Мы перебираем хэш и печатаем два числа, которые встречались только один раз.
Фрагмент C++ приведенного выше подхода выглядит следующим образом:
int n = nums.size();
vector<int> result;
if(n == 0) {
return result;
}
map<int, int> m;
for(int i = 0; i < n; i++) {
m[nums[i]]++;
}
vector<int> result;
for(auto i = m.begin(); i != m.end(); i++) {
if(i->second == 1) {
result.push_back(i->first);
}
}
return result;
Временная сложность программы составляет O(n), а пространственная сложность составляет O(n).
XOR-оператор
Программа может быть решена с временной сложностью O(n) и пространственной сложностью O(1) с использованием операции XOR.
Пусть a и b — элементы, встречающиеся ровно один раз в массиве nums. Сначала мы вычисляем XOR всех элементов массива.
xor = nums[0]^nums[1]^nums[2]....nums[n - 1]
Все биты, установленные в приведенной выше переменной xor, будут установлены в одном неповторяющемся элементе a или b.
Мы берем любой бит набора xor и делим элементы массива на два набора. Один набор элементов с одним и тем же установленным битом и другой с тем же самым битом, не установленным.
Мы делаем XOR для всех элементов в первом наборе, который возвращает первый неповторяющийся элемент, и делая то же самое в другом наборе, мы возвращаем второй неповторяющийся элемент.
Сначала проверим алгоритм.
- set xorResult = nums[0]
a = 0, b = 0, i = 0
vector<int> result
- loop for i = 1; i < nums.size(); i++
- xorResult ^= nums[i]
- set setBitNo = xorResult == INT_MIN ? 0 : xorResult & ~(xorResult - 1)
- loop for i = 0; i < nums.size(); i+=
- if nums[i] & setBitNo
- a ^= nums[i]
- else
- b ^= nums[i]
- result.push_back(a)
- result.push_back(b)
- return result
Временная сложность описанного выше подхода составляет O(n), а пространственная сложность — O(1).
Давайте проверим наш алгоритм на C++, Golang и Javascript.
С++ решение
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int xorResult = nums[0];
int a = 0, b = 0, i;
vector<int> result;
for(i = 1; i < nums.size(); i++) {
xorResult ^= nums[i];
}
int setBitNo = xorResult == INT_MIN ? 0 : xorResult & ~(xorResult - 1);
for(i = 0; i < nums.size(); i++) {
if(nums[i] & setBitNo) {
a ^= nums[i];
} else {
b ^= nums[i];
}
}
result.push_back(a);
result.push_back(b);
return result;
}
};
Голанг решение
func singleNumber(nums []int) []int {
xorResult := 0
for _, num := range nums {
xorResult = xorResult ^ num
}
setBitNo := xorResult & (-xorResult)
result := make([]int, 2)
for _, num := range nums {
if num & setBitNo == 0 {
result[0] ^= num
} else {
result[1] ^= num
}
}
return result
}
Javascript-решение
var singleNumber = function(nums) {
let xorResult = 0;
let a = 0, b = 0, i = 0;
for(i = 0; i < nums.length; i++){
xorResult ^= nums[i];
}
let setBitNo = xorResult & ~(xorResult - 1);
for(i = 0; i < nums.length; i++) {
if((nums[i] & setBitNo) === 0)
a ^= nums[i];
else
b ^= nums[i];
}
return [a, b];
};
Давайте протестируем наш алгоритм для примера 1.
Input: nums = [1, 2, 1, 3, 2, 5]
Step 1: xorResult = nums[0]
= 1
Step 2: int a = 0, b = 0, i
vector<int> result
Step 3: loop for i = 1; i < nums.size(); i++
xorResult ^= nums[i]
The xorResult is 6 (0110)
Step 4: setBitNo = xorResult == INT_MIN ? 0 : xorResult & ~(xorResult - 1)
= 6 == INT_MIN ? 0 : xorResult & ~(xorResult - 1)
= false ? 0 : xorResult & ~(xorResult - 1)
= xorResult & ~(xorResult - 1)
= 6 & ~(6 - 1)
= 6 & ~5
= 6 & -6
= 2
Step 5: loop for i = 0; i < nums.size()
0 < 6
true
if nums[i] & setBitNo
nums[0] & 2
1 & 2
0001 & 0010
0
false
else
b ^= nums[i]
= b ^ nums[i]
= 0 ^ nums[0]
= 0 ^ 1
= 1
i++
i = 1
Step 6: loop i < nums.size()
1 < 6
true
if nums[i] & setBitNo
nums[1] & 2
2 & 2
0010 & 0010
2
true
a ^= nums[i]
= a ^ nums[1]
= 0 ^ 2
= 2
i++
i = 2
Step 7: loop i < nums.size()
2 < 6
true
if nums[i] & setBitNo
nums[2] & 2
1 & 2
0001 & 0010
0
false
else
b ^= nums[i]
= b ^ nums[i]
= 1 ^ nums[2]
= 1 ^ 1
= 0
i++
i = 3
Step 8: loop i < nums.size()
3 < 6
true
if nums[i] & setBitNo
nums[3] & 2
3 & 2
0011 & 0010
2
true
a ^= nums[i]
= a ^ nums[3]
= 2 ^ 3
= 1
i++
i = 4
Step 9: loop i < nums.size()
4 < 6
true
if nums[i] & setBitNo
nums[4] & 2
2 & 2
0010 & 0010
2
true
a ^= nums[i]
= a ^ nums[4]
= 1 ^ 2
= 3
i++
i = 5
Step 10: loop i < nums.size()
5 < 6
true
if nums[i] & setBitNo
nums[5] & 2
5 & 2
0101 & 0010
0
false
else
b ^= nums[i]
= b ^ nums[i]
= 0 ^ nums[5]
= 0 ^ 5
= 5
i++
i = 6
Step 11: loop i < nums.size()
6 < 6
false
Step 12: result.push_back(a)
result.push_back(3)
result = [3]
result.push_back(b)
result.push_back(5)
result = [3, 5]
return result
We return the result as [3, 5].
Первоначально опубликовано на https://alkeshghorpade.me.
