2019-04-06 16:09:56
问题描述：
问题求解：
本题还是挺有难度的，主要是要考虑好如何去进行构造。
首先考虑到2 * A[i] = A[j] + A[k]，那么j，k就必须是同奇同偶，否则它们的和必为奇数，显然等式不成立。
那么如果我们将N的数组分成两个部分，一部分全奇数，一部分全偶数，并且这两个部分是Beautiful Array，那么将它们concat一下，得到的也是Beautiful Array。
那么如何得到这两个部分呢？
这就需要一些数学的证明了，很容易证明得到漂亮数组满足以下的两个性质。
- 同乘一个数依然是漂亮数组
- 同加一个数依然是漂亮数组
得到这两个性质后就可以进行构造了，从{1}开始，每次得到{A * 2 - 1}和{A * 2}，显然这两个数组是漂亮数组，并且分别是奇数和偶数数组，将它们concat之后就会得到长度更长的数组，这样就可以构造出来结果需要的数组。
public int[] beautifulArray(int N) {
List<Integer> res = new ArrayList<>();
res.add(1);
while (res.size() < N) {
List<Integer> tmp = new ArrayList<>();
for (int i : res) if (i * 2 - 1 <= N) tmp.add(i * 2 - 1);
for (int i : res) if (i * 2 <= N) tmp.add(i * 2);
res = tmp;
}
return res.stream().mapToInt(i -> i).toArray();
}