Question

667. Beautiful Arrangement II

中文文档

Description

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 = [a1, a2, a3, ... , an], then the list [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] has exactly k distinct integers.

Return _the list_ answer. If there multiple valid answers, return 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.

 

Constraints:

• 1 <= k < n <= 104

Solutions

Solution 1

class Solution:
  def constructArray(self, n: int, k: int) -> List[int]:
    l, r = 1, n
    ans = []
    for i in range(k):
      if i % 2 == 0:
        ans.append(l)
        l += 1
      else:
        ans.append(r)
        r -= 1
    for i in range(k, n):
      if k % 2 == 0:
        ans.append(r)
        r -= 1
      else:
        ans.append(l)
        l += 1
    return ans

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

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

func constructArray(n int, k int) []int {
  l, r := 1, n
  ans := make([]int, n)
  for i := 0; i < k; i++ {
    if i%2 == 0 {
      ans[i] = l
      l++
    } else {
      ans[i] = r
      r--
    }
  }
  for i := k; i < n; i++ {
    if k%2 == 0 {
      ans[i] = r
      r--
    } else {
      ans[i] = l
      l++
    }
  }
  return ans
}

function constructArray(n: number, k: number): number[] {
  let l = 1;
  let r = n;
  const ans = new Array(n);
  for (let i = 0; i < k; ++i) {
    ans[i] = i % 2 == 0 ? l++ : r--;
  }
  for (let i = k; i < n; ++i) {
    ans[i] = k % 2 == 0 ? r-- : l++;
  }
  return ans;
}