跳转至

1734. 解码异或后的排列

来源第 44 场双周赛 Q3难度中等分数2024

题目描述

给你一个整数数组 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 < 105
  • n 是奇数。
  • encoded.length == n - 1

解法

方法一：位运算

思考

\(\textit{perm}\) 是 \(1..n\) 的排列且 \(n\) 为奇数，\(\textit{encoded}[i]=\textit{perm}[i]\oplus\textit{perm}[i+1]\)。缺一个起始值便无法递推。

\(1\oplus\cdots\oplus n\) 可知。把 \(\textit{encoded}\) 的偶数下标异或起来，恰好比全集少了 \(\textit{perm}[n-1]\)，因此能还原末元。

从末元逆序用 \(\textit{perm}[i]=\textit{encoded}[i]\oplus\textit{perm}[i+1]\) 推出整个排列。

我们注意到，数组 \(perm\) 是前 \(n\) 个正整数的排列，因此 \(perm\) 的所有元素的异或和为 \(1 \oplus 2 \oplus \cdots \oplus n\)，记为 \(a\)。而 \(encode[i]=perm[i] \oplus perm[i+1]\)，如果我们将 \(encode[0],encode[2],\cdots,encode[n-3]\) 的所有元素的异或和记为 \(b\)，则 \(perm[n-1]=a \oplus b\)。知道了 \(perm\) 的最后一个元素，我们就可以通过逆序遍历数组 \(encode\) 求出 \(perm\) 的所有元素。

时间复杂度 \(O(n)\)，其中 \(n\) 为数组 \(perm\) 的长度。忽略答案数组的空间消耗，空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def decode(self, encoded: List[int]) -> List[int]:
        n = len(encoded) + 1
        a = b = 0
        for i in range(0, n - 1, 2):
            a ^= encoded[i]
        for i in range(1, n + 1):
            b ^= i
        perm = [0] * n
        perm[-1] = a ^ b
        for i in range(n - 2, -1, -1):
            perm[i] = encoded[i] ^ perm[i + 1]
        return perm

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] decode(int[] encoded) {
        int n = encoded.length + 1;
        int a = 0, b = 0;
        for (int i = 0; i < n - 1; i += 2) {
            a ^= encoded[i];
        }
        for (int i = 1; i <= n; ++i) {
            b ^= i;
        }
        int[] perm = new int[n];
        perm[n - 1] = a ^ b;
        for (int i = n - 2; i >= 0; --i) {
            perm[i] = encoded[i] ^ perm[i + 1];
        }
        return perm;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> decode(vector<int>& encoded) {
        int n = encoded.size() + 1;
        int a = 0, b = 0;
        for (int i = 0; i < n - 1; i += 2) {
            a ^= encoded[i];
        }
        for (int i = 1; i <= n; ++i) {
            b ^= i;
        }
        vector<int> perm(n);
        perm[n - 1] = a ^ b;
        for (int i = n - 2; ~i; --i) {
            perm[i] = encoded[i] ^ perm[i + 1];
        }
        return perm;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func decode(encoded []int) []int {
    n := len(encoded) + 1
    a, b := 0, 0
    for i := 0; i < n-1; i += 2 {
        a ^= encoded[i]
    }
    for i := 1; i <= n; i++ {
        b ^= i
    }
    perm := make([]int, n)
    perm[n-1] = a ^ b
    for i := n - 2; i >= 0; i-- {
        perm[i] = encoded[i] ^ perm[i+1]
    }
    return perm
}

评论