漂亮数组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 <= N <= 1000

# 思路

/* A 是漂亮数组，则 a * A + b 也是漂亮数组 
 * A 为奇数漂亮数组，B 为偶数漂亮数组，A + B 为漂亮数组
 * 数组两两配对，左数组 * 2 - 1 一定是奇数组，右数组 * 2 一定为偶数组，合并一定为漂亮数组
 * 假设 [1] 是最小漂亮数组，按照上面规律递推得到的一定是漂亮数组。 
 * |1|1|1|1|1|1|1|1|
 * |1 2|1 2|1 2|1 2|
 * |1 3 2 4|1 3 2 4|
 * |1 5 3 7 2 6 4 8|
 */

# 解法


class Solution {
    /* A 是漂亮数组，则 a * A + b 也是漂亮数组 
     * A 为奇数漂亮数组，B 为偶数漂亮数组，A + B 为漂亮数组
     * 数组两两配对，左数组 * 2 - 1 一定是奇数组，右数组 * 2 一定为偶数组，合并一定为漂亮数组
     * 假设 [1] 是最小漂亮数组，按照上面规律递推得到的一定是漂亮数组。 
     * |1|1|1|1|1|1|1|1|
     * |1 2|1 2|1 2|1 2|
     * |1 3 2 4|1 3 2 4|
     * |1 5 3 7 2 6 4 8|
     */
    public int[] beautifulArray(int N) {

        int[] a = new int[N];
        Arrays.fill(a, 1);
        part(a, 0, N - 1);
        return a;
    }
    public void part(int[] a, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        part(a, lo, mid);
        part(a, mid + 1, hi);
        for (int i = lo; i <= mid; i++) {
            a[i] = 2 * a[i] - 1;
        } 
        for (int i = mid + 1; i <= hi; i++) {
            a[i] = 2 * a[i];
        }
        return;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

# 总结

分析出几种情况，然后分别对各个情况实现