667 Beautiful Arrangement II
1. Question
Given two integersn
andk
, you need to construct a list which containsn
different positive integers ranging from1
ton
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 exactlyk
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
andk
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
得到最多4个差值得数组为
1, 5, 2, 4,3
差: 4, 3, 2, 1
我们发现规律是,将1 - n的数交错放在数组里,比如先放1,再放n, 然后放2,之后放n - 1,以此类推
class Solution {
public int[] constructArray(int n, int k) {
if (n == 0 || k <= 0 || k >= n) {
return new int[0];
}
int[] res = new int[n];
int start = 1, end = n;
for (int i = 0; start <= end; i++) {
// 当 K 等于 1时,将1-n的数字直接升序放在数组即可
if (k== 1) {
res[i] = start;
++start;
}
// 否则将start和end交错放在数组里
else {
if (k % 2 != 0) {
res[i] = start;
++start;
}
else {
res[i] = end;
--end;
}
--k;
}
}
return res;
}
}
3. Time & Space Complexity
时间复杂度O(n), 空间复杂度O(n)
Last updated
Was this helpful?