Leetcode-1734-解码异或后的排列

Leetcode-1734-解码异或后的排列

题目描述

• 给你一个整数数组 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

算法思路：异或性质

异或运算具有如下性质：

• 异或运算满足交换律和结合律；

• 任意整数和自身做异或运算的结果都等于 0，即x⊕x=0；

• 任意整数和 0 做异或运算的结果都等于其自身，即x⊕0=0⊕x=x。

实现算法分析：

• 这道题规定了数组perm 是前 n 个正整数的排列，其中 n 是奇数，只有充分利用给定的条件，才能得到答案。

• 为了得到原始数组perm，应首先得到数组 perm 的第一个元素（即下标为 0 的元素），这也是最容易得到的。

  • 如果能得到数组 perm 的全部元素的异或运算结果，以及数组 perm 除了 perm[0] 以外的全部元素的异或运算结果，即可得到perm[0] 的值。

    • 由于数组 perm 是前 n 个正整数的排列，因此数组 perm 的全部元素的异或运算结果即为从 1 到 n 的全部正整数的异或运算结果。用total 表示数组 perm 的全部元素的异或运算结果，则有

    

• 如何得到数组 perm 除了 perm[0] 以外的全部元素的异或运算结果？

  • 由于 n 是奇数，除了 perm[0] 以外，数组 perm 还有 n−1 个其他元素，n−1 是偶数，又由于数组encoded的每个元素都是数组perm 的两个元素异或运算的结果，因此数组 encoded 中存在 n-1/2个元素，这些元素的异或运算结果为数组perm除了perm[0]以外所有元素的异或和

  • 具体而言，数组 encoded 的所有下标为奇数的元素的异或运算结果即为数组 perm 除了 perm[0] 以外的全部元素的异或运算结果。用 odd 表示数组encoded 的所有下标为奇数的元素的异或运算结果，则有

    

• 根据 total 和 odd的值，即可计算得到 perm[0] 的值：

• 

• 由于perm[0] 已知，因此对 i 从 1 到 n−1 依次计算 perm[i] 的值，即可得到原始数组perm。

计算过程见「1720. 解码异或后的数组的官方题解」。

性质分析

class Solution {
    public int[] decode(int[] encoded) {
        // 1. 计算出perm[0]
        int total = 0;                                  // 1-n内所有数字的异或和
        int odd   = 0;                                  // encoded中所有奇数下标的异或和
        int n = encoded.length + 1;                     // perm 的数组长度
        for(int i = 1;i <= n;i++){                      // 计算1-n内所有数字的异或和
            total ^= i;
        }
        for(int i = 1;i < n - 1;i += 2){                // 计算除了perm[0]以外的异或和
            odd ^= encoded[i];
        }

        int[] perm = new int[n];
        perm[0] = total ^ odd;                          // perm [0]的值

        // 2. 力扣题号1720的逻辑：利用异或性质
        for(int i = 1;i < n;++i){
            perm[i] = perm[i - 1] ^ encoded[i - 1];
        }

        // 3. 返回结果
        return perm;
    }
}

复杂度分析

• 时间复杂度 ：O(n) , 其中n是原数组的长度，原因是要遍历encoded数组一次
• 空间复杂度 ：O(1) 注意空间复杂度不考虑返回值。

打赏