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

英文原文

Given two integers n and k, construct a list answer that contains n different positive integers ranging from 1 to n and obeys the following requirement:

• Suppose this list is answer = [a1, a2, a3, ... , an], then the list [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] has exactly k distinct integers.

Return the list answer. If there multiple valid answers, return any of them.

 

Example 1:

Input: n = 3, k = 1
Output: [1,2,3]
Explanation: The [1,2,3] has three different positive integers ranging from 1 to 3, and the [1,1] has exactly 1 distinct integer: 1

Example 2:

Input: n = 3, k = 2
Output: [1,3,2]
Explanation: The [1,3,2] has three different positive integers ranging from 1 to 3, and the [2,1] has exactly 2 distinct integers: 1 and 2.

 

Constraints:

• 1 <= k < n <= 104

中文题目

给你两个整数 n 和 k ，请你构造一个答案列表 answer ，该列表应当包含从 1 到 n 的 n 个不同正整数，并同时满足下述条件：

• 假设该列表是 answer = [a1, a2, a3, ... , an] ，那么列表 [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] 中应该有且仅有 k 个不同整数。

返回列表 answer 。如果存在多种答案，只需返回其中 任意一种 。

 

示例 1：

输入：n = 3, k = 1
输出：[1, 2, 3]
解释：[1, 2, 3] 包含 3 个范围在 1-3 的不同整数，并且 [1, 1] 中有且仅有 1 个不同整数：1

示例 2：

输入：n = 3, k = 2
输出：[1, 3, 2]
解释：[1, 3, 2] 包含 3 个范围在 1-3 的不同整数，并且 [2, 1] 中有且仅有 2 个不同整数：1 和 2

 

提示：

• 1 <= k < n <= 104

 

通过代码

官方题解

可以枚举 $[1, 2, …, n]$ 的排列，对于每一个排列，检查有多少个不同的整数，枚举全排列的时间复杂度是：$O(n!)$。注意到题目中给出的数据的范围：$1 \le k < n \le 10^4$，检查有多少个不同的整数还需要一次遍历，总的时间复杂度为 $O((n + 1)!)$，是不符合题目要求的。

方法：构造

如何避免枚举 $[1, 2, …, n]$ 的排列呢，需要我们观察一些特殊的用例：

• 顺序数组或者逆序数组：$[1, 2, 3, …, n]$ ，呈等差数列形式，此时公差为 $1$，即 $k = 1$；
• 最大值和最小值交错出现： $[1, n, 2, n-1, 3, n-2, ….]$，此时相邻的两个数的差的绝对值不会出现重复，$k$ 达到最大，$k = n - 1$。大家可以用一个具体的例子验证一下。

当 $n=6$ 和 $k=3$ 时，可以构造数组 $[1, 2, 3, 6, 4, 5]$ 是符合要求的，如何得到它们呢？

• 构造等差数列： $[1，2]$，此时题目中给出的差的列表为 $[1]$；
• 构造交错数列：$\text{[1，4，2，3]}$，此时题目中给出的差的列表为 $[3,2,1]$，再给每个元素加 $2$，得到 $[3，6，4，5]$。

代码的编写没有难度，一些加 $1$ 、减 $1$ 的地方大家如果弄不清楚的话，拿具体的例子（不要太特殊不容易发现一般规律，也不要太复杂，容易把自己绕晕）研究一下就可以了。

代码

[]
class Solution {

    public int[] constructArray(int n, int k) {
        int[] res = new int[n];

        // 第 1 步：构造等差数列，把 1 到 n - k - 1 赋值结果数组的前面
        for (int i = 0; i < n - k - 1; i++) {
            res[i] = i + 1;
        }

        // 第 2 步：构造交错数列，下标从 n - k - 1 开始，数值从 n - k 开始
        // 控制交错的变量
        int j = 0;

        int left = n - k;
        int right = n;
        for (int i = n - k - 1; i < n; i++) {
            if (j % 2 == 0) {
                res[i] = left;
                left++;
            } else {
                res[i] = right;
                right--;
            }
            j++;
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：$O(n)$；
• 空间复杂度：
  • 如果计算保存答案的数组的空间，空间复杂度为 $O(n)$；
  • 如果不计算保存答案的数组的空间，空间复杂度为 $O(1)$。

统计信息

通过次数	提交次数	AC比率
8336	13357	62.4%

提交历史

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

相似题目

题目	难度
优美的排列	中等