Question

667. 优美的排列 II

English Version

题目描述

给你两个整数 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, n, 2, n-1, 3,... 构造答案数据 ans 的前 $k$ 个数，共产生 $k-1$ 个不同的整数。然后根据 $k$ 的奇偶性确定从哪个数开始构造下一个数。

时间复杂度 $O(n)$，忽略答案数组的空间消耗，空间复杂度 $O(1)$。

class Solution:
  def constructArray(self, n: int, k: int) -> List[int]:
    l, r = 1, n
    ans = []
    for i in range(k):
      if i % 2 == 0:
        ans.append(l)
        l += 1
      else:
        ans.append(r)
        r -= 1
    for i in range(k, n):
      if k % 2 == 0:
        ans.append(r)
        r -= 1
      else:
        ans.append(l)
        l += 1
    return ans

class Solution {
  public int[] constructArray(int n, int k) {
    int l = 1, r = n;
    int[] ans = new int[n];
    for (int i = 0; i < k; ++i) {
      ans[i] = i % 2 == 0 ? l++ : r--;
    }
    for (int i = k; i < n; ++i) {
      ans[i] = k % 2 == 0 ? r-- : l++;
    }
    return ans;
  }
}

class Solution {
public:
  vector<int> constructArray(int n, int k) {
    int l = 1, r = n;
    vector<int> ans(n);
    for (int i = 0; i < k; ++i) {
      ans[i] = i % 2 == 0 ? l++ : r--;
    }
    for (int i = k; i < n; ++i) {
      ans[i] = k % 2 == 0 ? r-- : l++;
    }
    return ans;
  }
};

func constructArray(n int, k int) []int {
  l, r := 1, n
  ans := make([]int, n)
  for i := 0; i < k; i++ {
    if i%2 == 0 {
      ans[i] = l
      l++
    } else {
      ans[i] = r
      r--
    }
  }
  for i := k; i < n; i++ {
    if k%2 == 0 {
      ans[i] = r
      r--
    } else {
      ans[i] = l
      l++
    }
  }
  return ans
}

function constructArray(n: number, k: number): number[] {
  let l = 1;
  let r = n;
  const ans = new Array(n);
  for (let i = 0; i < k; ++i) {
    ans[i] = i % 2 == 0 ? l++ : r--;
  }
  for (let i = k; i < n; ++i) {
    ans[i] = k % 2 == 0 ? r-- : l++;
  }
  return ans;
}