動機

很玄，這沒看解答會知道?

Problem

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 = 4Output: [2,1,4,3]

Example 2:

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

 

Constraints:

  • 1 <= n <= 1000

Sol

beautiful的array，同時乘2或是同時減1都是beautiful

奇數加偶數一定是奇數

所以要從原本的array生奇數版與偶數版之後合起來，但要注意不能超過n

[1]
[2,1] or [1,2]
[3,1,2] or [2,1,3]
[2,1,4,3]
[3,1,2,5,4]

class Solution:
    def beautifulArray(self, n: int) -> List[int]:
        ret = [1]
        while len(ret) < n:
            ret = [x*2-1 for x in ret if x*2-1 <= n] + [x*2 for x in ret if x*2 <= n]
        return ret[:n]