【LeetCode】解码异或后的排列 Java 题解

关注

发布于: 2021 年 05 月 11 日

题目描述

给你一个整数数组 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]
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/decode-xored-permutation/著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

这个题目是位运算的应用。位运算就是基于整数的二进制表示进行的运算。由于计算机内部就是以二进制来存储数据，位运算是相当快的。
基本的位运算共 6 种，分别为按位与、按位或、按位异或、按位取反、左移和右移。
与，或，异或都是将两个整数作为二进制数，对二进制表示中的每一位逐一运算。
其中，与运算是两个对应位都是 1 时才为 1
或运算是有一个 1 时就为 1
异或运算是两个对应不同时才为 1

AC 代码

    public int[] decode(int[] encoded) {        int n = encoded.length + 1;        int total = 0;        for (int i = 1; i <= n; i++) {            total ^= i;        }        int odd = 0;        for (int i = 1; i < n - 1; i += 2) {            odd ^= encoded[i];        }
        int[] ans = new int[n];        ans[0] = total ^ odd;        for (int i = 0; i < n - 1; i++) {            ans[i + 1] = ans[i] ^ encoded[i];        }
        return ans;    }

复制代码

总结

上述代码的时间复杂度是 O(n), 空间复杂度是 O(1)
坚持每日一题，加油！

发布于: 2021 年 05 月 11 日阅读数: 8

原文链接:【http://xie.infoq.cn/article/ae62a0be59a906d7e516e53cd】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】解码异或后的排列 Java 题解

题目描述

思路分析

AC 代码

总结

HQ数字卡

评论