Постановка задачи
Вам дан целочисленный массив pref
размера n
. Найдите и верните массив arr размера n, который удовлетворяет:
- pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i].
Обратите внимание, что ^ обозначает операцию побитового исключающего ИЛИ.
Можно доказать, что ответ единственный.
Постановка задачи взята с: https://leetcode.com/problems/find-the-original-array-of-prefix-xor
Пример 1:
Input: pref = [5, 2, 0, 3, 1] Output: [5, 7, 2, 3, 2] Explanation: From the array [5, 7, 2, 3, 2] we have the following: - pref[0] = 5. - pref[1] = 5 ^ 7 = 2. - pref[2] = 5 ^ 7 ^ 2 = 0. - pref[3] = 5 ^ 7 ^ 2 ^ 3 = 3. - pref[4] = 5 ^ 7 ^ 2 ^ 3 ^ 2 = 1.
Пример 2:
Input: pref = [13] Output: [13] Explanation: We have pref[0] = arr[0] = 13.
Ограничения:
- 1 <= pref.length <= 10^5 - 0 <= pref[i] <= 10^6
Объяснение
Для оператора XOR у нас есть следующий набор операций.
a ^ b = c a ^ c = b Eg 5 ^ 7 = 2 5 ^ 2 = 7
Мы используем этот подход, чтобы вернуть исходный массив.
Сначала проверим алгоритм.
- set n = pref.size() - if n == 0 || n == 1 - return pref - loop for i = n - 1; i >= 1; i-- - pref[i] = pref[i] ^ pref[i - 1] - return pref
Временная сложность описанного выше подхода составляет O(n), а пространственная сложность — O(1).
Давайте проверим наш алгоритм на C++, Golang и JavaScript.
С++ решение
class Solution { public: vector<int> findArray(vector<int>& pref) { int n = pref.size(); if(n == 0 || n == 1) { return pref; } for(int i = n - 1; i >= 1; i--) { pref[i] ^= pref[i - 1]; } return pref; } };
Голанг решение
func findArray(pref []int) []int { n := len(pref) if n == 0 || n == 1 { return pref } for i := n - 1; i >= 1; i-- { pref[i] ^= pref[i - 1] } return pref }
JavaScript-решение
var findArray = function(pref) { let n = pref.length; if(n === 0 || n === 1) { return pref; } for(let i = n - 1; i >= 1; i--) { pref[i] ^= pref[i - 1]; } return pref; };
Давайте протестируем наш алгоритм для примера 1.
Input: pref = [5, 2, 0, 3, 1] Step 1: n = pref.size() = 5 Step 2: if n == 0 || n == 1 5 == 0 || 5 == 1 false Step 3: loop for i = n - 1; i >= 1; i-- i = 5 - 1 = 4 4 >= 1 true pref[i] = pref[i] ^ pref[i - 1] = pref[4] ^ pref[3] = 1 ^ 3 = 2 pref = [5, 2, 0, 3, 2] i-- i = 3 Step 4: loop for i >= 1 3 >= 1 true pref[i] = pref[i] ^ pref[i - 1] = pref[3] ^ pref[2] = 3 ^ 0 = 3 pref = [5, 2, 0, 3, 2] i-- i = 2 Step 5: loop for i >= 1 2 >= 1 true pref[i] = pref[i] ^ pref[i - 1] = pref[2] ^ pref[1] = 0 ^ 2 = 2 pref = [5, 2, 2, 3, 2] i-- i = 1 Step 6: loop for i >= 1 1 >= 1 true pref[i] = pref[i] ^ pref[i - 1] = pref[1] ^ pref[0] = 2 ^ 5 = 7 pref = [5, 7, 2, 3, 2] i-- i = 0 Step 7: loop for i >= 1 0 >= 1 false Step 8: return pref We return the answer as [5, 7, 2, 3, 2].
Первоначально опубликовано на https://alkeshghorpade.me.