LeetCode 667. Beautiful Arrangement II

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.

Note:

  1. The n and k are in the range 1 <= k < n <= 104.

Example

1
2
3
4
5
6
7
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.

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.

Solution

本题主要是构造目标数组,其元素之间的差值的不同个数为k。输入确定为[1, 2, ... n],想构造该数组,即需要Greedy的思想,构造尽可能多的不同差值的情况。我们可以使用Two Pointer,当K大于1的时候,需要分别从左右获取元素(构成不同大小的差值情况);当K等于1的时候,即不需要更多的差值,所以只需要升序取完剩下元素即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package com.leetcode.greedy;

public class _667_Beautiful_Arrangement_II {
// time: O(N)
// space: O(N) for output.
public int[] constructArray(int n, int k) {
int[] res = new int[n];
int left = 1, right = n;
for (int i = 0; i < n; i++) {
if (k > 1) {
// need more distinct difference;
res[i] = (k % 2 != 0 ? left++ : right--);
k--;
} else {
res[i] = left++;
}
}
return res;
}
}

Reference