题目
Given two integers n
and k
, you need to construct a list which contains n
different positive integers ranging from 1
to n
and obeys the following requirement:Suppose this list is [a1, a2, a3, ... , an], then the list [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] has exactly k
distinct integers.
If there are multiple answers, print 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.
Note:
- The
n
and k
are in the range 1 <= k < n <= 10^4.
题目大意
给定两个整数 n 和 k,你需要实现一个数组,这个数组包含从 1 到 n 的 n 个不同整数,同时满足以下条件:
- 如果这个数组是 [a1, a2, a3, ... , an] ,那么数组 [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] 中应该有且仅有 k 个不同整数;.
- 如果存在多种答案,你只需实现并返回其中任意一种.
解题思路
- 先考虑
k
最大值的情况。如果把末尾的较大值依次插入到前面的较小值中,形成 [1,n,2,n-1,3,n-2,……]
,这样排列 k
能取到最大值 n-1
。k
最小值的情况是 [1,2,3,4,……,n]
,k
取到的最小值是 1。那么 k
在 [1,n-1]
之间取值,该怎么排列呢?先顺序排列 [1,2,3,4,……,n-k-1]
,这里有 n-k-1
个数,可以形成唯一一种差值。剩下 k+1
个数,形成 k-1
种差值。
- 这又回到了
k
最大值的取法了。k
取最大值的情况是 n
个数,形成 n-1
个不同种的差值。现在 k+1
个数,需要形成 k
种不同的差值。两者是同一个问题。那么剩下 k
个数的排列方法是 [n-k,n-k+1,…,n]
,这里有 k
个数,注意代码实现时,注意 k
的奇偶性,如果 k
是奇数,“对半穿插”以后,正好匹配完,如果 k
是偶数,对半处的数 n-k+(k+1)/2
,最后还需要单独加入到排列中。
- 可能有读者会问了,前面生成了 1 种差值,后面这部分又生产了
k
种差值,加起来不是 k + 1
种差值了么?这种理解是错误的。后面这段最后 2 个数字是 n-k+(k+1)/2-1
和 n-k+(k+1)/2
,它们两者的差值是 1,和第一段构造的排列差值是相同的,都是 1。所以第一段构造了 1 种差值,第二段虽然构造了 k
种,但是需要去掉两段重复的差值 1,所以最终差值种类还是 1 + k - 1 = k
种。
代码
package leetcode
func constructArray(n int, k int) []int {
res := []int{}
for i := 0; i < n-k-1; i++ {
res = append(res, i+1)
}
for i := n - k; i < n-k+(k+1)/2; i++ {
res = append(res, i)
res = append(res, 2*n-k-i)
}
if k%2 == 0 {
res = append(res, n-k+(k+1)/2)
}
return res
}