Beautiful Arrangement II Problem
Description
LeetCode Problem 667.
Given two integers n and k, construct a list answer that contains n different positive integers ranging from 1 to n and obeys the following requirement:
- Suppose this list is answer = [a_1, a_2, a_3, … , a_n], then the list [|a_1 - a_2|, |a_2 - a_3|, |a_3 - a_4|, … , |a_n-1 - a_n|] has exactly k distinct integers.
Return the list answer. If there multiple valid answers, return any of them.
Example 1:
1
2
3
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:
1
2
3
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.
Constraints:
- 1 <= k < n <= 10^4
Sample C++ Code
We can construct the array in the following way:
1, k+1, 2, k, 3, k-1, …
The distance of this array is k, k-1, k-2, …, 2, 1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
vector<int> constructArray(int n, int k) {
int l = 1, r = k + 1;
vector<int> ans;
while (l <= r) {
ans.push_back(l++);
if (l <= r) ans.push_back(r--);
}
for (int i = k + 2; i <= n; i++)
ans.push_back(i);
return ans;
}
};