描述
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:
1 | Input: n = 3, k = 1 |
Example 2:
1 | Input: n = 3, k = 2 |
Note:
- The
n
andk
are in the range $1 <= k < n <= 10^4$.
分析
1…n 这样的序列,能组成的最大的差值为 n-1, n-2, … 1, 0, 因为 $1 <= k < n <= 10^4$,所以结果肯定是存在的,只是我们需要构造一个这样的序列。根据 k 的值依次写入最大,最小值,每次写入后 k 自减1,当 k 等于1时,按照升序取剩余的数即可。
n = 3, k = 2
3, 1, 2
n = 3, k = 1
1, 2, 3
解决方案1(Java)
1 | class Solution { |