---

0667. 优美的排列 II

• 标签：数组、数学
• 难度：中等

题目链接

• 0667. 优美的排列 II - 力扣

题目大意

描述：

给定两个整数 $n$ 和 $k$。

要求：

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

• 假设该列表是 $answer = [a_1, a_2, a_3, ..., a_n]$，那么列表 $[|a_1 - a_2|, |a_2 - a_3|, |a_3 - a_4|, ..., |a_{n-1} - a_n|]$ 中应该有且仅有 $k$ 个不同整数。

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

说明：

• $1 \le k \lt n \le 10^{4}$。

示例：

• 示例 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：构造法

思路 1：算法描述

这道题目要求构造一个包含 $1$ 到 $n$ 的排列，使得相邻元素的差值恰好有 $k$ 个不同的整数。

我们可以使用构造法来解决这个问题。观察发现：

• 如果数组是 $[1, 2, 3, ..., n]$，那么相邻元素的差值都是 $1$，只有 $1$ 个不同的整数。
• 如果数组是 $[1, n, 2, n-1, 3, n-2, ...]$，那么相邻元素的差值是 $n-1, n-2, n-3, ...$，有 $n-1$ 个不同的整数。

因此，我们可以先构造前 $k$ 个元素，使得它们的差值恰好有 $k$ 个不同的整数，然后剩余的元素按顺序排列。

具体步骤如下：

1. 初始化结果数组 $ans$。
2. 使用两个指针 $left = 1$ 和 $right = k + 1$，交替取值，构造前 $k + 1$ 个元素：
   • 先取 $left$，然后取 $right$，再取 $left + 1$，再取 $right - 1$，以此类推。
   • 这样可以保证前 $k + 1$ 个元素的差值恰好有 $k$ 个不同的整数。
3. 将剩余的元素 $[k + 2, k + 3, ..., n]$ 按顺序加入结果数组。
4. 返回结果数组 $ans$。

思路 1：代码

class Solution:
    def constructArray(self, n: int, k: int) -> List[int]:
        ans = []
        left, right = 1, k + 1
        
        # 构造前 k + 1 个元素，使得差值恰好有 k 个不同的整数
        while left <= right:
            ans.append(left)
            left += 1
            if left <= right:
                ans.append(right)
                right -= 1
        
        # 将剩余的元素按顺序加入结果数组
        for i in range(k + 2, n + 1):
            ans.append(i)
        
        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n)$。需要构造长度为 $n$ 的数组。
• 空间复杂度：$O(1)$。不考虑结果数组的空间，只使用了常数级别的额外空间。