Beautiful Arrangement II
题目描述:
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
nandkare in the range 1 <= k < n <= 104.
题目大意:
给定2个整数n和k，你需要使用1～n这n个数字构造一个数列。当然这个数列是需要满足一定要求的。假设这个数列是 [a1, a2, a3, ... , an],那么另一个数列 [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|]则只包含k个不同的元素。
其实我们只要让数列满足这样即可。[1, k+1, 2, k, 3, k-1, 4, k-2 ...]
我们也可以直接以1开头，然后相邻元素依次向差k, k-1, k-2, k-3...这点差值交给程序去判断。
题目代码:
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;}
};class Solution {
public:vector<int> constructArray(int n, int k) {int vis[n+1] = {0};vector<int> v;v.push_back(1);vis[1] = 1;int cnt = 0;for(int i = k; i > 0; i--){int a1 = v.back()-i;int a2 = v.back()+i;if(a1 > 0 && a1 <= n && !vis[a1]){v.push_back(a1); cnt++;vis[a1] = 1;}else if(a2 > 0 && a2 <=n && !vis[a2]){v.push_back(a2); cnt++;vis[a2] = 1;}}//剩余元素for(int i = 1; i <= n; i++){if(!vis[i]){v.push_back(i);vis[i] = 1;}}return v;}
};