Question

932. Beautiful Array

中文文档

Description

An array nums of length n is beautiful if:

• nums is a permutation of the integers in the range [1, n].
• For every 0 <= i < j < n, there is no index k with i < k < j where 2 * nums[k] == nums[i] + nums[j].

Given the integer n, return _any beautiful array _nums_ of length _n. There will be at least one valid answer for the given n.

 

Example 1:

Input: n = 4
Output: [2,1,4,3]

Example 2:

Input: n = 5
Output: [3,1,2,5,4]

 

Constraints:

• 1 <= n <= 1000

Solutions

Solution 1

class Solution:
  def beautifulArray(self, n: int) -> List[int]:
    if n == 1:
      return [1]
    left = self.beautifulArray((n + 1) >> 1)
    right = self.beautifulArray(n >> 1)
    left = [x * 2 - 1 for x in left]
    right = [x * 2 for x in right]
    return left + right

class Solution {
  public int[] beautifulArray(int n) {
    if (n == 1) {
      return new int[] {1};
    }
    int[] left = beautifulArray((n + 1) >> 1);
    int[] right = beautifulArray(n >> 1);
    int[] ans = new int[n];
    int i = 0;
    for (int x : left) {
      ans[i++] = x * 2 - 1;
    }
    for (int x : right) {
      ans[i++] = x * 2;
    }
    return ans;
  }
}

class Solution {
public:
  vector<int> beautifulArray(int n) {
    if (n == 1) return {1};
    vector<int> left = beautifulArray((n + 1) >> 1);
    vector<int> right = beautifulArray(n >> 1);
    vector<int> ans(n);
    int i = 0;
    for (int& x : left) ans[i++] = x * 2 - 1;
    for (int& x : right) ans[i++] = x * 2;
    return ans;
  }
};

func beautifulArray(n int) []int {
  if n == 1 {
    return []int{1}
  }
  left := beautifulArray((n + 1) >> 1)
  right := beautifulArray(n >> 1)
  var ans []int
  for _, x := range left {
    ans = append(ans, x*2-1)
  }
  for _, x := range right {
    ans = append(ans, x*2)
  }
  return ans
}