LeetCode - Beautiful Array

时间:2021-11-30 00:34:24
For some fixed N, an array A is beautiful if it is a permutation of the integers 1, 2, ..., N, such that:

For every i < j, there is no k with i < k < j such that A[k] * 2 = A[i] + A[j].

Given N, return any beautiful array A.  (It is guaranteed that one exists.)

Example 1:

Input: 4
Output: [2,1,4,3]
Example 2: Input: 5
Output: [3,1,2,5,4] Note: 1 <= N <= 1000

这道题是用divide and conque 做的。参考自: https://blog.csdn.net/lwgkzl/article/details/83502656

因为2*A[k]是偶数,如果要求2*A[K]!=A[I]+A[J]那么可以构造位置在A[k]左边的全部放奇数,位置在A[k]右边的全部放偶数。这样就保证了对于K位置而言,这个性质是满足的。

也许你就有疑问了,1,3,5,6,2,4.这组序列中,虽然对于6位置而言,左边全是奇数,右边全是偶数,但是全是奇数的那一边明显不满足要求。怎么解决呢?

习惯从幼儿园开始就要养成,左边是奇数,右边是偶数的形式也得从N比较小的时候开始。这里有一个递归的思想。因为长度为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.(满足题目性质)

那么 2*Beautiful Array((N+1)/2)-1(奇数在前)连接  2*Beautiful Array(N/2) = 1  5  3  7 | 2  6  4.(逐个元素进行操作)

我们可以观察到,对于这个分隔符而言,左边是奇数,右边是偶数,所以在分隔符位置,无疑是满足题目要求的性质的。而且,左边的奇数是从满足题目性质的数组进行线性运算得出的,所以并不会影响各个位置数字间的性质,(如1,3,5. 2*3==1+5,同时乘2之后这个性质依然成立)。既然组成这个大数组的子数组Beautiful Array(N/2)和Beautiful Array((N+1)/2)都满足性质,那么乘法之后的数组也依然满足题目要求。所以大数组左半部分和右半部分都满足题目要求。而中间分隔位置也满足性质,所以这一整个大数组也满足题目性质了。所以我们只需要保证Beautiful Array(1)满足题目性质就可以递推出所有的Beautiful Array(N)了。很明显Beautiful Array(1)没有别的选择,只能满足性质。

class Solution {
public int[] beautifulArray(int N) {
int[] res = new int[N];
if(N == 1){
res[0] = 1;
return res;
}
else{
int[] arr1 = beautifulArray ((N+1)/2);
for(int i = 0; i<arr1.length; i++){
res[i] = 2*arr1[i] - 1;
}
int[] arr2 = beautifulArray(N/2); for(int i= arr1.length; i<arr1.length+arr2.length; i++){
res[i] = 2*arr2[i - arr1.length];
}
}
return res;
}
}