There is an integer array perm
that is a permutation of the first n
positive integers, where n
is always odd.
It was encoded into another integer array encoded
of length n - 1
, such that encoded[i] = perm[i] XOR perm[i + 1]
. For example, if perm = [1,3,2]
, then encoded = [2,1]
.
Given the encoded
array, return the original array perm
. It is guaranteed that the answer exists and is unique.
Example 1:
Input: encoded = [3,1] Output: [1,2,3] Explanation: If perm = [1,2,3], then encoded = [1 XOR 2,2 XOR 3] = [3,1]
Example 2:
Input: encoded = [6,5,4,6] Output: [2,4,1,5,3]
Constraints:
3 <= n < 105
n
is odd.encoded.length == n - 1
Solution: XOR
The key is to find p[0]. p[i] = p[i – 1] ^ encoded[i – 1]
- p[0] ^ p[1] ^ … ^ p[n-1] = 1 ^ 2 ^ … ^ n
- encoded[1] ^ encode[3] ^ … ^ encoded[n-2] = (p[1] ^ p[2]) ^ (p[3] ^ p[4]) ^ … ^ (p[n-2] ^ p[n-1])
1) xor 2) = p[0]
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua class Solution { public: vector<int> decode(vector<int>& encoded) { const int n = encoded.size() + 1; vector<int> perm(n); // p[0] = (p[0]^p[1]^...^p[n-1] = 1^2^...^n) // ^ (p[1]^p[2]^...^p[n-1]) for (int i = 1; i <= n; ++i) perm[0] ^= i; for (int i = 1; i < n; i += 2) perm[0] ^= encoded[i]; for (int i = 1; i < n; ++i) perm[i] = perm[i - 1] ^ encoded[i - 1]; return perm; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment