LeetCode 932. 漂亮数组 JAVA

对于某些固定的 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）A是一个漂亮数组，如果对A中所有元素添加一个常数，那么Ａ还是一个漂亮数组。

（2）A是一个漂亮数组，如果对A中所有元素乘以一个常数，那么A还是一个漂亮数组。

（3）A是一个漂亮数组，如果删除一些A中一些元素，那么A还是一个漂亮数组。

（4) A是一个奇数构成的漂亮数组，B是一个偶数构成的漂亮数组，那么A+B也是一个漂亮数组
比如:{1,5,3,7}+{2,6,4,8}={1,5,3,7,2,6,4,8}也是一个漂亮数组。

所以我们假设一个{1-m}的数组是漂亮数组，可以通过下面的方式构造漂亮数组{1-2m}:

对{1-m}中所有的数乘以2-1，构成一个奇数漂亮数组A。如{1,3,2,4},可以得到{1,5,3,7}
对{1-m}中所有的数乘以2,构成一个偶数漂亮数组B,如{1,3,2,4}, 可以得到{2,6,4,8}
A+B构成了{1-2m}的漂亮数组。{1,5,3,7}+{2,6,4,8}={1,5,3,7,2,6,4,8}
从中删除不要的数字即可。

class Solution {
public int[] beautifulArray(int N) {
int array[] = new int[2000];
int array2[] = new int[N];
int k =0;
array[0] = 2;
array[1] = 1;
array[2] = 4;
array[3] = 3;
for(int i = 1;i<200;i*=2){
for(int j = 0;j<i*4;j++){
array[i*4+j] = array[j]*2;
array[j] = array[j]*2-1;
}
}
for(int i = 0;i<2000;i++){
if(k<N&&array[i]!=0&&array[i]<=N){
array2[k] = array[i];
k++;
}
}
return array2;
}
}

最后

以上就是勤劳楼房为你收集整理的LeetCode 932. 漂亮数组 JAVA的全部内容，希望文章能够帮你解决LeetCode 932. 漂亮数组 JAVA所遇到的程序开发问题。

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