667 Beautiful Arrangement II

# 1. Question

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
2
3
Output: [1, 2, 3]
4
5
Explanation:
6
The [1, 2, 3] has three different positive integers ranging from 1 to 3, and the [1, 1] has exactly 1 distinct integer: 1.
Copied!
Example 2:
1
Input: n = 3, k = 2
2
3
Output: [1, 3, 2]
4
5
Explanation:
6
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.
Copied!
Note:
1. 1.
The`n`and`k`are in the range 1 <= k < n <= 10^4.

# 2. Implementation

(1) 当K等于1时，显然直接将1-n升序放在数组即可
(2) 当K大于1时，我们可以发现K最大的可能值是n - 1，比如当n = 5时，数组为
1， 2， 3， 4，5

1， 5， 2， 4，3

1
class Solution {
2
public int[] constructArray(int n, int k) {
3
if (n == 0 || k <= 0 || k >= n) {
4
return new int;
5
}
6
7
int[] res = new int[n];
8
int start = 1, end = n;
9
10
for (int i = 0; start <= end; i++) {
11
// 当 K 等于 1时，将1-n的数字直接升序放在数组即可
12
if (k== 1) {
13
res[i] = start;
14
++start;
15
}
16
// 否则将start和end交错放在数组里
17
else {
18
if (k % 2 != 0) {
19
res[i] = start;
20
++start;
21
}
22
else {
23
res[i] = end;
24
--end;
25
}
26
--k;
27
}
28
}
29
return res;
30
}
31
}
Copied!