> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/google/667-beautiful-arrangement-ii.md).

# 667 Beautiful Arrangement II

## 667. [Beautiful Arrangement II](https://leetcode.com/problems/beautiful-arrangement-ii/description/)

## 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:**

```
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.

## 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，以此类推

```java
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)