Beautiful Arrangement II

Description

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:

1. The n and k are in the range 1 <= k < n <= $10^4$ .

Solutions

My solution

Idea: place k numbers in an alternating way: [1, n, 2, n-1, 3, n-2, ...], so there are k - 1 distinct absolute differences. Then place the remaining numbers in increasing or decreasing order. That is, the last distinct absolute difference is 1.

class Solution {
public:
    vector<int> constructArray(int n, int k) {
        vector<int> ans(n);
        for(int i = 0; i < k / 2; ++i){
            ans[2 * i] = i + 1;
            ans[2 * i + 1] = n - i;
        }
        int diff, start;
        if(k % 2){
            diff = 1;
            start = k / 2 + 1;
        }else{
            diff = -1;
            start = n - k / 2;
        }
        for(int i = k / 2 * 2; i < n; ++i){
            ans[i] = start;
            start += diff;
        }
        return ans;
    }
};

A better solution

Idea: put first k + 1 numbers in the order [1, k+1, 2, k, 3, ...], which forms k distinct distances [k, k-1, ..., 1]. Let's say this is the first part. Then the second part is formed by putting the remaining numbers in increasing order. Note the distance between the last element of the first part and first element of the second part is in [k, k-1, ..., 1]. And adding the second part will not produce a new distance.

Reference: https://leetcode.com/problems/beautiful-arrangement-ii/discuss/106957/C++-concise-code-O(n)

class Solution {
public:
    vector<int> constructArray(int n, int k) {
        vector<int> ans(n);
        int s = 1, l = k + 1;
        for(int i = 0; i < k + 1; ++i){
            ans[i] = i % 2 ? l-- : s++;
        }
        for(int i = k + 1; i < n; ++i){
            ans[i] = i + 1;
        }
        return ans;
    }
};