0667. 优美的排列 II【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 构造

1. 📝 题目描述

• leetcode

给你两个整数 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 <= 10^4

2. 🎯 s.1 - 构造

c

int* constructArray(int n, int k, int* returnSize) {
    int* res = (int*)malloc(sizeof(int) * n);
    *returnSize = n;
    int lo = 1, hi = n;
    for (int i = 0; i < n; i++) {
        if (k > 1) {
            if (k % 2 == 1) res[i] = lo++;
            else res[i] = hi--;
            k--;
        } else {
            res[i] = lo++;
        }
    }
    return res;
}

js

/**
 * @param {number} n
 * @param {number} k
 * @return {number[]}
 */
var constructArray = function (n, k) {
  const res = []
  let lo = 1,
    hi = n
  for (let i = 0; i < n; i++) {
    if (k > 1) {
      if (k % 2 === 1) res.push(lo++)
      else res.push(hi--)
      k--
    } else {
      res.push(lo++)
    }
  }
  return res
}

py

class Solution:
    def constructArray(self, n: int, k: int) -> List[int]:
        res = []
        lo, hi = 1, n
        for _ in range(n):
            if k > 1:
                if k % 2 == 1:
                    res.append(lo); lo += 1
                else:
                    res.append(hi); hi -= 1
                k -= 1
            else:
                res.append(lo); lo += 1
        return res

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

算法思路：

• 交替从前后两端取值可产生 k-1 个不同差值，剩余位置顺序填充
• 当 k > 1 时，奇数位取小端 lo，偶数位取大端 hi
• k 消耗完后，剩余位置递增填充