【Day 70 】2024-06-16 - 932. 漂亮数组

[azl397985856]

932. 漂亮数组

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/beautiful-array/

前置知识

• 分治

  题目描述

  
  对于某些固定的 N，如果数组 A 是整数 1, 2, ..., N 组成的排列，使得：

对于每个 i < j，都不存在 k 满足 i < k < j 使得 A[k] * 2 = A[i] + A[j]。

那么数组 A 是漂亮数组。

 

给定 N，返回任意漂亮数组 A（保证存在一个）。

 

示例 1：

输入：4 输出：[2,1,4,3]

示例 2：

输入：5 输出：[3,1,2,5,4]

 

提示：

1 <= N <= 1000

 

[xy147]

js代码

const beautifulArray = function (n) {
  let arr = [];
  arr.push(1);
  while (arr.length < n) {
    let tmp = [];
    for (const i of arr) if (i * 2 - 1 <= n) tmp.push(i * 2 - 1);
    for (const i of arr) if (i * 2 <= n) tmp.push(i * 2);
    arr = tmp;
  }

  return arr;
};

复杂度分析

时间复杂度：O(nlogn) 空间复杂度：O(n+logn)

[zhiyuanpeng]

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

[Dtjk]

class Solution { public: vector beautifulArray(int n) { if(n==1)return {1}; vector res; auto left=beautifulArray(n-n/2); auto right=beautifulArray(n/2); for(auto& x:left){ res.push_back(2x-1); } for(auto& x:right){ res.push_back(2x); } return res; } };

[smallppgirl]

class Solution:
    def beautifulArray(self, n: int) -> List[int]:
        memo = {1: [1]}
        def f(N):
            if N not in memo:
                odds = f((N+1)//2)
                evens = f(N//2)
                memo[N] = [2*x-1 for x in odds] + [2*x for x in evens]
            return memo[N]
        return f(n)