解码异或后的排列

力扣 1734. 解码异或后的排列

题目说明

给你一个整数数组 perm ，它是前 n 个正整数的排列，且 n 是个奇数。

它被加密成另一个长度为 n - 1 的整数数组 encoded ，满足 encoded[i] = perm[i] XOR perm[i + 1] 。比方说，如果 perm = [1,3,2] ，那么 encoded = [2,1] 。

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

提示：
- 3 <= n < 105
- n 是奇数。
- encoded.length == n - 1

示例

例 1：

1
2
3

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

例 2：

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

笔者理解

此题是一道位运算算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，发现此题因为答案是唯一确定的且元素个数为奇数，可以用异或的性质来进行求解，涉及到的基础性质在之前数组异或操作有讲解，让我们来看看具体如何实现的吧。

实现

public int[] decode(int[] encoded) {
        int n = encoded.length + 1;
        int[] result = new int [n];

        // 前n个数的异或值 即a0^a1^a2...
        int sum;

        // 之前“数组异或操作”中已经解释，这里不在赘述
        switch (n % 4) {
            case 0:
                sum = n;
                break;
            case 1:
                sum = 1;
                break;
            case 2:
                sum = n + 1;
                break;
            default:
                sum = 0;
        }

        // encoded中偶数元素的异或值
        // 即e1^e3^e5^....
        // 因为e1 = a1^a2
        //     e3 = a3^a4
        //     e5 = a5^a6
        //     .......
        // 所以evenSum = a1^a2^a3^a4....
        // 而sum = a0^a1^a2....
        // 因为异或的性质 a^b = c  b^c = a
        // 所以a0 = sum^evenSum
        int evenSum = 0;

        for (int i = 1; i < n - 1; i+=2) {
            evenSum ^= encoded[i];
        }

        int first = sum ^ evenSum;
        result[0] = first;

        // 得知a0和encoded数组就可以推出原数组了
        for (int i = 1; i < n; i++) {
            first ^= encoded[i - 1];
            result[i] = first;
        }

        return result;
    }