问题描述
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， 那么对于k个不同差异值的要求来说， 1和k+1必须相邻，然后k+1和2必须相邻（差异值为k-1），然后2和k相邻（差异值k-2），以此类推，可以得出以下排列方式:
1 k+1 2 k 3 k-1 4 k-2 …
(注意 奇数位 和 偶数位 的规律)
我们令 start = 1, tail = k+1; 那么排列终止条件即为 taik < start
按照以上规则排列完毕后，我们再在数组末尾加上[k+2, n]之间的元素即可
示例代码
func constructArray(n int, k int) []int {
ans := []int{}
start := 1
tail := k + 1
for {
if tail < start {
break
}
ans = append(ans, start)
start++
if len(ans) == k+1 {
break
}
ans = append(ans, tail)
tail--
if len(ans) == k+1 {
break
}
}
for i := k + 2; i <= n; i++ {
ans = append(ans, i)
}
return ans
}