本文共 2248 字，大约阅读时间需要 7 分钟。

题目：

HintsSubmissionsDiscussSolution 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

解释：

尝试使用分治法来做，所以把数组分为left和right两块： 一种方法是分·[1, N / 2] 和[N / 2 + 1, N]，但是在merge的时候会出现问题。 另一种方法是分为奇数块odd和偶数块even，也就是奇数块odd在左边，偶数快even在右边 所以没有k能够使得 A[k] * 2 = odd + even，

Disscuss区的作者遍历了N=5d的所有的排列：

找到了20 个beautiful array ，其中只有4个不满足 odd + even 的模式: [2, 1, 4, 5, 3] [3, 1, 2, 5, 4] [3, 5, 4, 1, 2] [4, 5, 2, 1, 3]

beautiful array满足的条件是：

不存在 i < k < j, 使得 A[k] * 2 = A[i] + A[j]

对beautiful array 进行下列3种变换，可以得到新的beautiful array

1. 删除

   很好证明

2. 加法

   若A[k] * 2 != A[i] + A[j],
   则(A[k] + x) * 2 = A[k] * 2 + 2x != A[i] + A[j] + 2x = (A[i] + x) + (A[j] + x)
   E.g: [1,3,2] + 1 = [2,4,3].

3. 乘法

   若A[k] * 2 != A[i] + A[j],
   则(A[k] * x) * 2 = A[k] * 2 * x != (A[i] + A[j]) * x = (A[i] * x) + (A[j] * x)

E.g: [1,3,2] * 2 = [2,6,4]

根据上述三个法则，我们可以很方便地构造 beautiful array。

假设我们有一个长度为N的beautiful array A A1 = A * 2 - 1是一个只包含 1 到N * 2 -1中的奇数的 beautiful array A2 = A * 2是一个只包含 2 到 N * 2中的偶数的 beautiful array B = A1 + A2 是一个长度为N * 2的 beautiful array

为什么A1+A2是 beautiful array？

因为，首先A是beautiful array，所以A1和A2都分别是beautiful array，也就是说，在A1和A2的内部，是满足约束条件的，现在就是要考虑有没有一种可能，A[i]在A1中，A[j]在A2中，使得 A[k] * 2 = A[i] + A[j]：

很显然，这种情况是不存在的，因为A[i]在A1中是奇数，A[j]在A2中是偶数，他们俩相加一定是奇数，所以不可能是哪个整数的2倍。

E.g:

A = [2, 1, 4, 5, 3] A1 = [3, 1, 7, 9, 5] A2 = [4, 2, 8, 10, 6] B = A1 + A2 = [3, 1, 7, 9, 5, 4, 2, 8, 10, 6]

然后，分治法需要用递归或者循环来实现。

python代码：

class Solution:    def beautifulArray(self, N):        """        :type N: int        :rtype: List[int]        """        res=[1]        while len(res)

c++代码：

class Solution {
   public:    vector
   
     beautifulArray(int N) {
           vector
    
      res={
   1};        while (res.size()