LeetCode - Beautiful Array

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;

    }

}

巴特西

LeetCode - Beautiful Array

最新文章

热门文章