题目

给你两个整数 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、遍历；时间复杂度O(n)，空间复杂度O(n)

func constructArray(n int, k int) []int {
   if n == k {
      return nil
   }
   res := make([]int, n)
   // 构建等差数列为1：共n-k个数=>1
   for i := 1; i <= n-k; i++ {
      res[i-1] = i
   }
   // 构建交错队列：最大值和最小值交错出现，这样差值各不相同
   // n=10, k=7 => [1 2 3 4 5 6 7 10 8 9]
   // 剩下k个数（与等差数列相连）：共k个差值，依次1、2、3、...，去除1后共k-1个差值
   left := n - k + 1
   right := n
   count := 0
   for i := n - k + 1; i <= n; i++ {
      if count%2 == 1 {
         res[i-1] = left
         left++
      } else {
         res[i-1] = right
         right--
      }
      count++
   }
   return res
}

总结

Medium题目，需要找到规律来生成数组