原文链接: https://leetcode-cn.com/problems/beautiful-array

英文原文

An array nums of length n is beautiful if:

• nums is a permutation of the integers in the range [1, n].
• For every 0 <= i < j < n, there is no index k with i < k < j where 2 * nums[k] == nums[i] + nums[j].

Given the integer n, return any beautiful array nums of length n. There will be at least one valid answer for the given n.

 

Example 1:

Input: n = 4
Output: [2,1,4,3]

Example 2:

Input: n = 5
Output: [3,1,2,5,4]

 

Constraints:

• 1 <= n <= 1000

中文题目

对于某些固定的 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_1, a_2, \cdots, a_n]$ 是漂亮的，那么对这个数组进行仿射变换，得到的新数组 $[ka_1+b, ka_2+b, \cdots, ka_n+b]$ 也是漂亮的（其中 $k \neq 0$）。那么我们就有了一个想法：将数组分成两部分 left 和 right，分别求出一个漂亮的数组，然后将它们进行仿射变换，使得不存在满足下面条件的三元组：

• A[k] * 2 = A[i] + A[j], i < k < j；
• A[i] 来自 left 部分，A[j] 来自 right 部分。

可以发现，等式 A[k] * 2 = A[i] + A[j] 的左侧是一个偶数，右侧的两个元素分别来自两个部分。要想等式恒不成立，一个简单的办法就是让 left 部分的数都是奇数，right 部分的数都是偶数。

因此我们将所有的奇数放在 left 部分，所有的偶数放在 right 部分，这样可以保证等式恒不成立。对于 [1..N] 的排列，left 部分包括 (N + 1) / 2 个奇数，right 部分包括 N / 2 个偶数。对于 left 部分，我们进行 k = 1/2, b = 1/2 的仿射变换，把这些奇数一一映射到不超过 (N + 1) / 2 的整数。对于 right 部分，我们进行 k = 1/2, b = 0 的仿射变换，把这些偶数一一映射到不超过 N / 2 的整数。经过映射，left 和 right 部分变成了和原问题一样，但规模减少一半的子问题，这样就可以使用分治算法解决了。

算法

在 [1..N] 中有 (N + 1) / 2 个奇数和 N / 2 个偶数。我们将其分治成两个子问题，其中一个为不超过 (N + 1) / 2 的整数，并映射到所有的奇数；另一个为不超过 N / 2 的整数，并映射到所有的偶数。

[sol1]
class Solution {
    Map<Integer, int[]> memo;
    public int[] beautifulArray(int N) {
        memo = new HashMap();
        return f(N);
    }

    public int[] f(int N) {
        if (memo.containsKey(N))
            return memo.get(N);

        int[] ans = new int[N];
        if (N == 1) {
            ans[0] = 1;
        } else {
            int t = 0;
            for (int x: f((N+1)/2))  // odds
                ans[t++] = 2*x - 1;
            for (int x: f(N/2))  // evens
                ans[t++] = 2*x;
        }
        memo.put(N, ans);
        return ans;
    }
}

[sol1]
class Solution:
    def beautifulArray(self, N):
        memo = {1: [1]}
        def f(N):
            if N not in memo:
                odds = f((N+1)/2)
                evens = f(N/2)
                memo[N] = [2*x-1 for x in odds] + [2*x for x in evens]
            return memo[N]
        return f(N)

复杂度分析

• 时间复杂度：$O(N \log N)$，代码中的函数 f 执行的次数为 $O(\log N)$，每次执行的时间复杂度为 $O(N)$。

• 空间复杂度：$O(N \log N)$。

统计信息

通过次数	提交次数	AC比率
9036	14196	63.7%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言