leetcode 1734. Decode XORed Permutation

题目概述

解题思路

我首先打印了一下N=3和N=5的时候的各种情况的encoded的值，试图找到思路，可惜未果。

然后我开始分析，我发现，由于异或运算有这样一个性质：

(a ^ b) ^ (b ^ c) = a ^ 0 ^ c = a ^ c

我们就可以得到第一个元素和后面n - 1个元素的异或的结果：

a[0] ^ a[1], a[0] ^ a[2], ......, a[0] ^ a[n - 1]

接下来，我们要做的就是求出a[0]。该怎么计算呢？还是利用上面的性质，如果我们把a[0] ^ a[1] ^ ... ^ a[n - 1]和上面的 n-1个值一起异或，得到的结果为：

(a[0] ^ a[1] ^ ... ^ a[n - 1]) ^ (a[0] ^ a[1]) ^ (a[0] ^ a[2]) ^ ... ^ (a[0] ^ a[n - 1])
= (a[0] ^ a[0] ^ ... ^ a[0])  # n 个 a[0] 
^ (a[1] ^ a[1])
^ ...
^ (a[n - 1] ^ a[n - 1])
= a[0]

得到了a[0]就可以计算a[1]~a[n - 1]了。

方法性能

方法的时间复杂度为O(n):

示例代码

class Solution {
public:
	vector<int> decode(vector<int>& encoded) 
	{
		int len = encoded.size() + 1;
		//get the first number
		vector<int> xors;
		int te = 0, fir = 0;
		for (int i = 0; i < len - 1; ++i)
		{
			te ^= encoded[i];
			fir ^= i + 1;
			fir ^= te;
			xors.push_back(te);
		}
		fir ^= len;


		vector<int> res{fir};

		for (int i = 0; i < len - 1; ++i)
			res.push_back(res[i] ^ encoded[i]);

		return res;
	}
};