05 August 2008
对于某些固定的 N，如果数组 A 是整数 1, 2, …, N 组成的排列，使得：
对于每个 i < j，都不存在 k 满足 i < k < j 使得 A[k] * 2 = A[i] + A[j]。
那么数组 A 是漂亮数组。
给定 N，返回任意漂亮数组 A（保证存在一个）。
1
2
3
4
5
6
7
8
9
10
示例 1：
输入：4
输出：[2,1,4,3]
示例 2：
输入：5
输出：[3,1,2,5,4]
题目要求不能让该等式成立：A[k] * 2 = A[i] + A[j]，i < k < j，可知等式左边必为偶数，只要右边和为奇数即可保证不成立
可知 奇数 + 偶数 = 奇数，那就让A[i]和A[j]一个为奇数一个为偶数即可，不妨让A[i]为奇数，A[j]为偶数
也就是我们要新建一个数组，数组长度为N，所有奇数都在前半部分，所有偶数都在后半部分，但并不是简单的奇偶的堆砌，比如[1, 3, 5, 2, 4]这样是不对的，可以看后面的解释
还有要用到的数学知识是，如果一个数组是漂亮数组，那么其线性变换之后的数组也是漂亮数组，即如果[x1, x2, x3]是一个漂亮数组，则[k * x1 + b, k * x2 + b, k * x3 + b] 也一定是漂亮数组。这是本题能用分治思想的核心所在，
时间复杂度：O(nlogn)，f(N)调用logn次，每次时间消耗O(n)
空间复杂度：O(nlogn)，f(N)调用logn次形成大小为logn的递归栈，每次需要长度为n的数组存储结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
Map<Integer, int[]> memo;
public int[] beautifulArray(int n) {
memo = new HashMap<>();
memo.put(1, new int[]{1});
return f(n);
}
private int[] f(int N){
if(!memo.containsKey(N)){
int index = 0;
int[] res = new int[N];
for(int x : f((N + 1) / 2)){
res[index++] = 2 * x - 1;
}
for(int x : f(N / 2)){
res[index++] = 2 * x;
}
memo.put(N, res);
}
return memo.get(N);
}
}