Medium

题目描述

有一个整数数组 perm，它是前 n 个正整数的排列，其中 n 总是奇数。

它被编码成另一个长度为 n - 1 的整数数组 encoded，其中 encoded[i] = perm[i] XOR perm[i + 1]。例如，如果 perm = [1,3,2]，那么 encoded = [2,1]。

给你 encoded 数组，返回原始数组 perm。题目保证答案存在且唯一。

示例 1：

输入：encoded = [3,1]
输出：[1,2,3]
解释：如果 perm = [1,2,3]，那么 encoded = [1 XOR 2,2 XOR 3] = [3,1]

示例 2：

输入：encoded = [6,5,4,6]
输出：[2,4,1,5,3]

提示：

  • 3 <= n < 10^5
  • n 是奇数
  • encoded.length == n - 1

解题思路

这道题的关键在于利用异或运算的性质和题目给出的条件来求解原始排列。

核心思路：

  1. 利用异或性质求 perm[0]：

    • 首先计算 1 到 n 所有数的异或值：total = 1 XOR 2 XOR ... XOR n
    • 由于 encoded[i] = perm[i] XOR perm[i+1]，我们有：
      • encoded[1] = perm[1] XOR perm[2]
      • encoded[3] = perm[3] XOR perm[4]
      • …（所有奇数索引位置）
    • 计算所有奇数索引位置的异或值：oddXor = encoded[1] XOR encoded[3] XOR ...
    • 根据异或性质，perm[0] = total XOR oddXor

  2. 为什么这样可行？

    • total 包含了所有 perm[i]
    • oddXor 包含了除 perm[0] 外的所有元素（每个元素出现偶数次会被消除）
    • 因此 perm[0] = total XOR oddXor

  3. 还原完整数组：

    • 有了 perm[0] 后，利用 perm[i] = perm[i-1] XOR encoded[i-1] 依次求出所有元素

这个解法巧妙地利用了 n 为奇数这个条件，确保了奇数索引位置能够覆盖除第一个元素外的所有元素。

时间复杂度： O(n)，只需要遍历数组一次 空间复杂度： O(1)，除了结果数组外只使用常数空间

代码实现

class Solution {
public:
    vector<int> decode(vector<int>& encoded) {
        int n = encoded.size() + 1;
        
        // 计算1到n的异或值
        int total = 0;
        for (int i = 1; i <= n; i++) {
            total ^= i;
        }
        
        // 计算奇数索引位置的异或值
        int oddXor = 0;
        for (int i = 1; i < encoded.size(); i += 2) {
            oddXor ^= encoded[i];
        }
        
        // 求出第一个元素
        vector<int> perm(n);
        perm[0] = total ^ oddXor;
        
        // 依次求出其他元素
        for (int i = 1; i < n; i++) {
            perm[i] = perm[i-1] ^ encoded[i-1];
        }
        
        return perm;
    }
};

class Solution:
    def decode(self, encoded: List[int]) -> List[int]:
        n = len(encoded) + 1
        
        # 计算1到n的异或值
        total = 0
        for i in range(1, n + 1):
            total ^= i
        
        # 计算奇数索引位置的异或值
        odd_xor = 0
        for i in range(1, len(encoded), 2):
            odd_xor ^= encoded[i]
        
        # 求出第一个元素
        perm = [0] * n
        perm[0] = total ^ odd_xor
        
        # 依次求出其他元素
        for i in range(1, n):
            perm[i] = perm[i-1] ^ encoded[i-1]
        
        return perm

public class Solution {
    public int[] Decode(int[] encoded) {
        int n = encoded.Length + 1;
        
        // 计算1到n的异或值
        int total = 0;
        for (int i = 1; i <= n; i++) {
            total ^= i;
        }
        
        // 计算奇数索引位置的异或值
        int oddXor = 0;
        for (int i = 1; i < encoded.Length; i += 2) {
            oddXor ^= encoded[i];
        }
        
        // 求出第一个元素
        int[] perm = new int[n];
        perm[0] = total ^ oddXor;
        
        // 依次求出其他元素
        for (int i = 1; i < n; i++) {
            perm[i] = perm[i-1] ^ encoded[i-1];
        }
        
        return perm;
    }
}

/**
 * @param {number[]} encoded
 * @return {number[]}
 */
var decode = function(encoded) {
    const n = encoded.length + 1;
    
    // 计算1到n的异或值
    let total = 0;
    for (let i = 1; i <= n; i++) {
        total ^= i;
    }
    
    // 计算奇数索引位置的异或值
    let oddXor = 0;
    for (let i = 1; i < encoded.length; i += 2) {
        oddXor ^= encoded[i];
    }
    
    // 求出第一个元素
    const perm = new Array(n);
    perm[0] = total ^ oddXor;
    
    // 依次求出其他元素
    for (let i = 1; i < n; i++) {
        perm[i] = perm[i-1] ^ encoded[i-1];
    }
    
    return perm;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要遍历数组计算异或值和还原数组
空间复杂度O(1)除了结果数组外，只使用常数额外空间

相关题目