[LeetCode]Beautiful Array

这道题我没有什么好的思路，看了讨论区和答案才知道怎么做。首先我们有几个推论:

• 如果A是beautiful array并且全为奇数，B是beautiful array并且全为偶数。那么AB或者BA也是beautiful array。AB代表把AB连接起来，BA同理。

这个很好解释，因为2 * AB[k]一定是偶数，所有不存在分散于A和B当中的三元组满足AB[i] + AB[j] = 2 * AB[k]，因为AB[i] + AB[j]分别在A和B当中所以一定为奇数。

另外，如果A是beautiful array，那么:

• A中的所有元素加上x之后仍然是beautiful array
• (A[k] + x) * 2 = A[k] * 2 + 2 * x != A[i] + A[j] + 2 * x =(A[i] + x) + (A[j] + x)
• A中的额所有元素乘以x之后也仍然是beautiful array
• A[k] * x * 2 != (A[i] + A[j]) * x = A[i] * x + A[j] * x
• 如果A是beautiful array，我们删除其中的某些元素后也仍然是beautiful array

有了以上的几个结论，我们就可以由小的beautiful array开始构建大的array。比如对于1-N组成的beautiful array A，我们可以对其每个元素进行操作:

• A[i] -> 2 * A[i] - 1, 这样新的矩阵是奇数组成的并且仍然是beautiful array
• A[i] -> 2 * A[i]，这样新的矩阵是偶数组成的并且仍然是beautiful array

奇数array和偶数array拼接之后也仍然是beautiful array。如果我们想求1-M组成的beautiful array，N < M <= 2*N，我们删掉一些元素即可。时间复杂度O(N * log N)，代码如下:

	class Solution {
	public:
	vector<int> beautifulArray(int N) {
	vector<int> res = { 1 };
	while (res.size() < N)
	{
	vector<int> tmp;
	for (const auto& i : res)if (2 * i - 1 <= N)tmp.push_back(2 * i - 1);
	for (const auto& i : res)if (2 * i <= N)tmp.push_back(2 * i);
	res = tmp;
	}
	return res;
	}
	};

view raw Beautiful Array.cpp hosted with ❤ by GitHub