对于某些固定的 N，如果数组 A 是整数 1, 2, ..., N 组成的排列，使得：
对于每个 i < j，都不存在 k 满足 i < k < j 使得 A[k] * 2 = A[i] + A[j]。
那么数组 A 是漂亮数组。
给定 N，返回任意漂亮数组 A（保证存在一个）。
示例 1：
输入：4
输出：[2,1,4,3]
示例 2：
输入：5
输出：[3,1,2,5,4]
提示：
1 <= N <= 1000
解法
方法一：分治法
因为2A[k]是偶数，如果要求2A[K]!=A[I]+A[J]那么可以构造位置在A[k]左边的全部放奇数，位置在A[k]右边的全部放偶数。这样就保证了对于K位置而言，这个性质是满足的。
而在1,3,5,6,2,4这组序列中，虽然对于6位置而言，左边全是奇数，右边全是偶数，但是全是奇数的那一边明显不满足要求。怎么解决呢？
这里有一个递归的思想。因为长度为N的序列中，奇数个数为（N+1）/2，偶数个数为N/2，所以Beautiful Array（N）的排列，可以由Beautiful Array(N/2)和Beautiful Array((N+1)/2)组成，为什么这么说呢？
假设N = 7，那么Beautiful Array(N/2) = 1,3,2（满足题目性质） Beautiful Array((N+1)/2) = 1,3,2,4（满足题目性质）
那么 2Beautiful Array((N+1)/2)-1（奇数在前）连接 2Beautiful Array(N/2) = 1 5 3 7 | 2 6 4.（逐个元素进行操作）
class Solution {
Map<Integer, int[]> memo;
public int[] beautifulArray(int N) {
memo = new HashMap();
return f(N);
}
public int[] f(int N) {
if (memo.containsKey(N))
return memo.get(N);
int[] ans = new int[N];
if (N == 1) {
ans[0] = 1;
} else {
int t = 0;
for (int x: f((N+1)/2)) // 奇数
ans[t++] = 2*x - 1;
for (int x: f(N/2)) // 偶数
ans[t++] = 2*x;
}
memo.put(N, ans);
return ans;
}
}
