Leetcode 2433 - Find The Original Array of Prefix Xor

題目

Problem#

給你一個整數陣列 pref 長度 n，要你回傳一個新的陣列，滿足條件：pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i]
答案保證唯一。

測資限制#

• $1 \le n \le 10^5$
• $0 \le val \le 10^6$

想法#

XOR 有以下特性：a ^ b = c, c ^ b = a, c ^ a = b
觀察範例後不難得出: b[i] = b[0]^b[1]^...^b[i-1]^a[i]，根據此觀察撰寫程式即可

AC Code#

Copy

class Solution {
public:
    vector<int> findArray(vector<int>& pref)
    {
        int n = pref.size();
        vector<int> ans = {pref[0]};
 
        int tmp = ans[0];
        for(int i = 1; i < n; i++)
        {
            tmp ^= pref[i];
            ans.push_back(tmp);
            tmp ^= pref[i];
            tmp ^= ans.back();
        }
 
        return ans;
    }
};

view raw leetcode/2433.cpp delivered with ❤ by emgithub

• 時間複雜度: $\mathcal{O}(n)$
• 空間複雜度: $\mathcal{O}(n)$

賞析#

後來看題解才知道原來 b[i] = a[i] ^ a[i-1] 就夠了

Copy

class Solution2 {
public:
    vector<int> findArray(vector<int>& pref)
    {
        int n = pref.size();
        vector<int> ans = {pref[0]};
        for(int i = 1; i < n; i++)
        {
            ans.push_back(pref[i]^pref[i-1]);
        }
 
        return ans;
    }
};

view raw leetcode/2433.cpp delivered with ❤ by emgithub