JAVA程序设计：漂亮数组（LeetCode：933）

对于某些固定的 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

思路：为了不存在a[k]*2=a[i]+a[j]，我们观察这个式子，可以发现等号左端为偶数，我们可以让右端为奇数从而满足条件，需要保证a[i]和a[j]一个为奇数，一个为偶数，我们可以将数组拆分成两部分，其中一部分为奇数，另一部分为偶数，之后通过分治的策略构造出漂亮数组。

class Solution {
Map<Integer,int[]> map;
public int[] beautifulArray(int N) {
map=new HashMap<>();
return f(N);
}
private int[] f(int N) {
if(map.containsKey(N))
return map.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;
}
map.put(N, ans);
return ans;
}
}

最后

以上就是壮观飞机为你收集整理的JAVA程序设计：漂亮数组（LeetCode：933）的全部内容，希望文章能够帮你解决JAVA程序设计：漂亮数组（LeetCode：933）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。