【Day 70 】2022-02-19 - 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

 

[ZJP1483469269]

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

[yetfan]

思路 没研究明白，直接抄了=。=

代码

class Solution:
    def beautifulArray(self, N):
        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)

复杂度 时间 O(nlogn) 空间 O(nlogn)

[QinhaoChang]

def beautifulArray(self, n): res = [1] while len(res) < n: res = [i 2 - 1 for i in res] + [i 2 for i in res] return [i for i in res if i <= n]

[feifan-bai]

思路 1.分治

代码

class Solution:
    def beautifulArray(self, n: int) -> List[int]:
        @lru_cache(None)
        def dp(n):
            if n == 1:
                return [1]
            ans = []
            # [1,n] 中奇数比偶数多1或一样
            for a in dp(n - n // 2):
                ans += [a * 2 - 1]
            for b in dp(n // 2):
                ans += [b * 2]
            return ans

        return dp(n)

复杂度分析

• 时间复杂度：O(NlogN)
• 空间复杂度：O(N+logN)

[zhangzz2015]

思路

• 这题比较tricky，主要是 奇数 + 偶数 = 奇数 ！= 2 数。因此把 n划分为奇数和偶数，进行分治，同时奇数 array[1 3 5] = arary[ 1 2 3] 2 -1 ，另外array[2 4 6] = array[ 1 2 3] * 2 。可利用递归后序遍历方法。时间复杂度为O(n^2)，因为有合并两个数组操作。空间复杂度为O(n)

关键点

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    vector<int> beautifulArray(int n) {

        //   array[1 n]      array[1 3 5 ..]=  array[1 2 3]*2 -1    array[2 4 6]=  array[1 2 3] *2 

        return dfs(n); 
    }

    vector<int>  dfs(int n)
    {

        if(n==1)
            return {1}; 

        vector<int> oddVec = dfs(n/2); 
        vector<int> evenVec = dfs(n- n/2); 
        vector<int> ret; 
        for(int i=0; i< oddVec.size(); i++)
            ret.push_back(oddVec[i]*2); 
        for(int i=0; i< evenVec.size(); i++)
            ret.push_back(evenVec[i]*2-1);         
        return ret;         
    }

};

[moirobinzhang]

Code:

public class Solution { Dictionary<int, int[]> memoDict;

public int[] BeautifulArray(int n) {
    memoDict = new Dictionary<int, int[]>();

    return BeautifulHelper(n);
}

public int[] BeautifulHelper(int n)
{
    if (memoDict.ContainsKey(n))
        return memoDict[n];

    int[] res = new int[n];
    if (n == 1)
    {
        res[0] = 1;
    }
    else
    {
        int t = 0;
        foreach(int x in BeautifulHelper((n + 1) / 2))
            res[t++] = 2* x - 1;
        foreach(int x in BeautifulHelper((n) / 2))
            res[t++] = 2* x;            
    }

    memoDict.Add(n, res);
    return res; 
}

}

[rzhao010]

class Solution {
    Map<Integer, int[]> memo ;
    public int[] beautifulArray(int n) {
        memo = new HashMap<>();
        memo.put(1, new int[]{1});
        return f(n);
    }

    private int[] f(int n) {
        if (!memo.containsKey(n)) {
            int index = 0;
            int[] res = new int[n];
            for (int x : f((n + 1)/ 2)) {
                res[index++] = 2 * x - 1;
            }
            for (int x : f(n / 2)) {
                res[index++] = 2 * x;
            }
            memo.put(n, res);
        }
        return memo.get(n);
    }
}

Complexity Time: O(nlogn) Space: O(nlogn)

[CoreJa]

思路

• 分治法+数学：题目的难点在于线性变化与奇偶组合。

  • 奇偶组合：题目给出的条件$2*nums[k]!=nums[i]+numsj$比较难应用。对于自然数而言，一定有$奇+偶=奇$，套用到上面的公式，考虑一个beautiful array全都是奇数，另一个beautiful array全是偶数，则两者拼接起来也必然满足条件。
  • 线性变化：一个beautiful array通过线性变化后仍然是beautiful array(相当于是条件的不等号两边同时乘系数k再加常数b，仍然保持不等。

  所以我们可以通过线性变化在已知的beautiful array构造全为奇数/偶数的beautiful array。例如[1,3,2]，全部乘2就全为偶数，全部乘2后-1就全为奇数，两者拼接仍为beautiful array。具体的，[1]可以视作递归的base case，把n分为n//2和n-n//2两部分，分别递归调用，把调用的结果分别进行线性变化使其分别全为奇数和偶数，最后拼在一起。递归树深度为$O(\log n)$，每次操作要执行n次，复杂度$O(n\log n)$。

• 递推分治+数学：改进上面的思路。答案可以从base case直接迭代出来，即由base case [1]可以进行x次线性变化的扩张得到长度为$2^x$的beautiful array。最后返回的答案剔除大于n的结果即可。复杂度$O(n\log n)$

代码

class Solution:
    # 分治法+数学：题目的难点在于线性变化与奇偶组合。
    # - 奇偶组合：题目给出的条件$2*nums[k]!=nums[i]+nums[j](i<k<j)$比较难应用。对于自然数而言，一定有$奇+偶=奇$，套用到
    #   上面的公式，考虑一个beautiful array全都是奇数，另一个beautiful array全是偶数，则两者拼接起来也必然满足条件。
    # - 线性变化：一个beautiful array通过线性变化后仍然是beautiful array(相当于是条件的不等号两边同时乘系数k再加常数b，
    #   仍然保持不等。
    # 所以我们可以通过线性变化在已知的beautiful array构造全为奇数/偶数的beautiful array。例如`[1,3,2]`，全部乘2就全为偶
    # 数，全部乘2后-1就全为奇数，两者拼接仍为beautiful array。具体的，`[1]`可以视作递归的base case，把`n`分为`n//2`和
    # `n-n//2`两部分，分别递归调用，把调用的结果分别进行线性变化使其分别全为奇数和偶数，最后拼在一起。递归树深度为$O(\log n)$，每次操作要执行n次，复杂度$O(n\log n)$。
    @cache
    def beautifulArray(self, n: int) -> List[int]:
        if n == 1:
            return [1]
        return [num * 2 for num in self.beautifulArray(n // 2)] + \
               [num * 2 - 1 for num in self.beautifulArray(n - n // 2)]

    # 递推分治+数学：改进上面的思路。答案可以从base case直接迭代出来，即由base case `[1]`可以进行x次线性变化的扩张得到长度
    # 为$2^x$的beautiful array。最后返回的答案剔除大于n的结果即可。复杂度$O(n\log n)$
    def beautifulArray2(self, n: int) -> List[int]:
        ans = [1]
        i = n << 1
        while i := i >> 1:
            ans = [num * 2 for num in ans] + [num * 2 - 1 for num in ans]
        return [num for num in ans if num <= n]

[ZhiweiZhen]

分治

class Solution:
    def beautifulArray(self, N: int) -> List[int]:
        @lru_cache(None)
        def dp(n):
            if n == 1:
                return [1]
            ans = []
            # [1,n] 中奇数比偶数多1或一样
            for a in dp(n - n // 2):
                ans += [a * 2 - 1]
            for b in dp(n // 2):
                ans += [b * 2]
            return ans

        return dp(N)

[Tesla-1i]

class Solution:
    def beautifulArray(self, N):
        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)

[googidaddy]

class Solution: def beautifulArray(self, n: int) -> List[int]: @lru_cache(None) def dp(n): if n == 1: return [1] ans = []

[1,n] 中奇数比偶数多1或一样

        for a in dp(n - n // 2):
            ans += [a * 2 - 1]
        for b in dp(n // 2):
            ans += [b * 2]
        return ans

    return dp(n)

[yan0327]

func beautifulArray(n int) []int {
    if n == 1{
        return []int{1}
    }
    arr := make([]int,0)
    odds := beautifulArray((n+1)>>1)
    evens := beautifulArray(n>>1)
    for _, o := range odds{
        arr = append(arr,2*o-1)
    }
    for _,e := range evens{
        arr = append(arr,2*e)
    }
    return arr
}

[alongchong]

class Solution {
    Map<Integer, int[]> memo;
    public int[] beautifulArray(int N) {
        memo = new HashMap();
        return f(N);
    }

    public int[] f(int N) {
        if (memo.containsKey(N))
            return memo.get(N);

        int[] ans = new int[N];
        if (N == 1) {
            ans[0] = 1;
        } else {
            int t = 0;
            for (int x: f((N+1)/2))  // odds
                ans[t++] = 2*x - 1;
            for (int x: f(N/2))  // evens
                ans[t++] = 2*x;
        }
        memo.put(N, ans);
        return ans;
    }
}

[xinhaoyi]

class Solution { private Map<Integer, int[]> memory = new HashMap(); public int[] beautifulArray(int n) { int[] temp = memory.get(n); if(temp != null) return temp;

    int[] result = new int[n];

    // result数组的访问下标 这里使用ArrayList更简洁
    int i = 0; 

    if(n != 1){
        // 这里注意哈 (n + 1) / 2 + n / 2 = n 整数除法有个向下取整 
        // 所以当n为奇数时 左半区元素比右边要多一个 习惯就好 
        for(int num : beautifulArray((n + 1)/ 2)) 
            result[i++] = num * 2 - 1;

        for(int num : beautifulArray(n / 2))
            result[i++] = num * 2;
    } 
    else result[0] = 1;

    memory.put(n, result);
    return result;
}

}

[junbuer]

思路

• 分治法

  代码

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

  复杂度分析

• 时间复杂度：$O(nlogn)$
• 空间复杂度：$O(nlogn)$

[FlorenceLLL]

思路

数学道理：

• [x, y, z] 如果是漂亮数组，那么[2x+k, 2y+k, 2z+k] 也是漂亮数组
• odd + even = odd, 2 * any number = odd, seperate array into even part then odd part, also keep even part as beautiful array and odd part as beautiful array
  • 1 - N integers has (N+1)/2 odds and N/2 odds, so we can find 1 - (N+1)/2 integers beautiful array and then change to odds in range 1 - N, same to evens
  • find 1 - N/2 or 1- (N+1)/2 range's beautiful array recursively, base case N = 1, array is [1]

Coding

class Solution {
    private Map<Integer, int[]> memo;
    public int[] beautifulArray(int n) {
        memo = new HashMap<>();
        memo.put(1, new int[]{1});
        return find(n);

    }

    private int[] find(int n) {
        if(!memo.containsKey(n)) {
            int index = 0;
            int[] res = new int[n];
            for (int x : find((n+1)/2)) {
                res[index++] = 2 * x - 1;
            }

            for (int x : find(n/2)) {
                res[index++] = 2 * x;
            }

            memo.put(n, res);
        }

        return memo.get(n);
    }
}

Complexity

Time complexity: O(NlogN), call find(n) n/2 times, each find(n) 's time complexity is O(logN) \n Space complexity: O(NlogN)\n

[biaohuazhou]

思路

分治

代码

    class Solution {
    Map<Integer, int[]> memo;
    public int[] beautifulArray(int N) {
        memo = new HashMap();
        return f(N);
    }

    public int[] f(int N) {
        if (memo.containsKey(N))
            return memo.get(N);

        int[] ans = new int[N];
        if (N == 1) {
            ans[0] = 1;
        } else {
            int t = 0;
            for (int x: f((N+1)/2))  // odds
                ans[t++] = 2*x - 1;
            for (int x: f(N/2))  // evens
                ans[t++] = 2*x;
        }
        memo.put(N, ans);
        return ans;
    }
}

复杂度分析 时间复杂度： O(NlogN) 空间复杂度：O(NlogN)

[haixiaolu]

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

• Time: O(nlogn)
• Space: O(nlogn)

[CodingProgrammer]

思路

今天的分治技巧性太强，抄的答案，拓展下知识面

代码

class Solution {
    Map<Integer, int[]> memo;
    public int[] beautifulArray(int n) {
        if (n < 1) {
            throw new IllegalArgumentException();
        }
        this.memo = new HashMap<>();
        this.memo.put(1, new int[]{1});
        return dfs(n);
    }

    private int[] dfs(int n) {
        if (!this.memo.containsKey(n)) {
            int[] ans = new int[n];
            int idx = 0;

            for (int odd : dfs((n + 1) / 2)) {
                ans[idx++] = 2 * odd - 1;
            }

            for (int even : dfs(n / 2)) {
                ans[idx++] = 2 * even;
            }

            this.memo.put(n, ans);
        }
        return this.memo.get(n);
    }
}

复杂度

• 时间复杂度： O(NlogN)
• 空间复杂度：O(NlogN)

[1149004121]

932. 漂亮数组

思路

分而治之。如果arr{n} 是漂亮数组，则对其进行kx+b的映射也是漂亮数组。如果 A 和 B 分别是不同奇偶性的漂亮数组，那么将 A 和 B 拼接起来仍为漂亮数组。因此对漂亮数组arr{n /2} 分别做奇偶映射，则arr_{n} 一定也是漂亮数组。

代码

var beautifulArray = function(n) {
    let arr = [1];
    if(n === 1) return arr;
    while(arr.length < n){
        let temp = [];
        for(let item of arr){
            if(item * 2 - 1 <= n) temp.push(item * 2 - 1);
        };
        for(let item of arr){
            if(item * 2 <= n) temp.push(item * 2);
        };
        arr = temp;
    };
    return arr;
};

复杂度分析

• 时间复杂度：O(N * logN)。
• 空间复杂度：O( N )。

[cszys888]

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)
                even = f(N//2)
                memo[N] = [i*2-1 for i in odds] + [i*2 for i in even]
            return memo[N]
        return f(n)

time complexity: O(nlogn) space complexity: O(nlogn)

[LannyX]

思路

分治

代码

class Solution {
    Map<Integer, int[]> memo = new HashMap<>();
    public int[] beautifulArray(int n) {
        memo.put(1, new int[]{1});
        return f(n);
    }
    private int[] f(int n){
        if(!memo.containsKey(n)){
            int index = 0;
            int[] res = new int[n];
            for(int x : f((n + 1) / 2)){
                res[index++] = 2 * x - 1;
            }
            for(int x : f(n / 2)){
                res[index++] = 2 * x;
            }
            memo.put(n, res);
        }
        return memo.get(n);
    }
}

复杂度分析

• 时间复杂度：O(nlogn)
• 空间复杂度：O(nlogn)

[liuzekuan]

思路

• 分治法

代码

• 语言支持：Java

Java Code:

class Solution {
    public int[] beautifulArray(int N) {
        int [] tmp = new int[N];
        int [] res = new int[N];
        if(N == 1){return new int[]{1};}
        if(N == 2){return new int[]{1,2};}
        if(N == 3){return new int[]{1,3,2};}
        int a = N % 2 == 0 ? N / 2 :  (N + 1)/ 2;
        int b = a % 2 == 0 ? a / 2 :  (a - 1)/ 2;
        for(int i = 0;i < N ;i++){
            tmp[i] = i + 1;
        }
        res = getRes(tmp,0,N - 1,2);

        return res;
    }

    public int[] getRes(int [] nums,int sta,int end,int time) {
        if(end - sta == 1){return nums;}
        if(end - sta == 2){
            int a = nums[sta + 1];
            nums[sta + 1] = nums[end];
            nums[end] = a;
            return nums;}
        //分两部分
        int an = nums[sta];
        int bn = nums[sta + 1];
        for(int i = sta;i <= (end + sta) / 2;i++){
            nums[i] = an + (i - sta) * time;
        }
        for(int i = ((end + sta) / 2)+ 1;i <= end;i++){
            nums[i] = bn + (i - (((end + sta) / 2 )+ 1)) * time;
        }
        nums = getRes(nums,sta,(sta + end) / 2,time * 2);
        nums = getRes(nums,((sta + end) / 2) + 1,end,time * 2);
        return nums;
    }
}

[xuhzyy]

class Solution(object):
    def beautifulArray(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        memo = {1: [1]}

        def f(n):
            if n not in memo:
                memo[n] = [2 * x - 1 for x in f((n+1)//2)] + [2 * x for x in f(n//2)]
            return memo[n]

        return f(n)

[zhiyuanpeng]

class Solution:
    def beautifulArray(self, N: int) -> List[int]:
        @lru_cache(None)
        def dp(n):
            if n == 1:
                return [1]
            ans = []
            # [1,n] 中奇数比偶数多1或一样
            for a in dp(n - n // 2):
                ans += [a * 2 - 1]
            for b in dp(n // 2):
                ans += [b * 2]
            return ans

        return dp(N)

[falconruo]

思路:

分治 odd + even != even

复杂度分析:

• 时间复杂度: O(nlogn)，n为给定整数
• 空间复杂度: O(n), 辅助数组长度

代码(C++):

class Solution {
public:
    vector<int> beautifulArray(int n) {
        vector<int> res{1};

        while (res.size() < n) {
            vector<int> tmp;
            for (int num : res)
                if (2 * num - 1 <= n)
                    tmp.push_back(2 * num - 1);

            for (int num : res)
                if (2 * num <= n)
                    tmp.push_back(2 * num);

            res = tmp;
        }

        return res;
    }
};

[wenlong201807]

代码块

var beautifulArray = function (n) {
  const map = new Map();
  map.set(1, [1]); // 初始化，也是截止条件
  const recursion = (n) => {
    if (map.has(n)) return map.get(n); // 递归的终止条件
    // 奇数放在左侧 -- 按照数组长度排列好漂亮数组后，然后再通过 2N-1 的方式转成当前层的奇数
    const left = recursion((n + 1) >> 1).map((item) => item * 2 - 1);
    const right = recursion(n >> 1).map((item) => item * 2);
    const ret = [...left, ...right];
    map.set(n, ret);
    return ret;
  };
  return recursion(n);
};

时间复杂度和空间复杂度

• 时间复杂度 O(n)
• 空间复杂度 O(1)

[iambigchen]

代码

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(n) 空间复杂度： O(n)

[Arya-03]

class Solution:
    def beautifulArray(self, N):
        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)

[Aobasyp]

思路 利用数学基本性质奇数 + 偶数 = 奇数

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

    return res;
}

};

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

[Myleswork]

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

    return res;
}

};

[charlestang]

思路

分治法。

时间复杂度 O(n log n)

空间复杂度 O(n log n)

代码

class Solution:
    def beautifulArray(self, n: int) -> List[int]:
        def shuffle(arr: List[int]) -> List[int]:
            if len(arr) == 1: return arr
            return shuffle(arr[0::2]) + shuffle(arr[1::2])
        return shuffle([i + 1 for i in range(n)])

[guangsizhongbin]

class Solution { Map<Integer, int[]> memo; public int[] beautifulArray(int N) { memo = new HashMap(); return f(N); }

public int[] f(int N) {
    if (memo.containsKey(N))
        return memo.get(N);

    int[] ans = new int[N];
    if (N == 1) {
        ans[0] = 1;
    } else {
        int t = 0;
        for (int x: f((N+1)/2))  // odds
            ans[t++] = 2*x - 1;
        for (int x: f(N/2))  // evens
            ans[t++] = 2*x;
    }
    memo.put(N, ans);
    return ans;
}

}

[15691894985]

【day70】932. 漂亮数组

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

思路：满足题干要求的，转换为奇数+偶数=奇数

性质1：如果数组A是漂亮数组，A中每个数x进行kx+b映射，其仍为漂亮数组

性质2：数组A和B是不同奇偶性的漂亮数组，那么A\B拼接起来仍为漂亮数组

求N长度的漂亮数组，那么一定有N/2个偶数和N-N/2个奇数 ，可以变换为全部为偶数的漂亮数组和全部为奇数的漂亮数组，递归求

class Solution:
    def beautifulArray(self,    N: int) -> List[int]:
        @lru_cache(None)
        def dp(n):
            if n ==1 :
                return[1]
            ans = []
            for a in dp(n-n//2):
                ans.append(a * 2-1)
            for b in dp(n // 2):
                ans.append(b * 2)
            return ans
        return dp(N)

复杂度分析：

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

[chakochako]

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

[Jay214]

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;
};

[hulichao]

思路

代码

class Solution {
    public int[] beautifulArray(int N) {
        int[] a = new int[N];
        Arrays.fill(a, 1);
        part(a, 0, N - 1);
        return a;
    }
    public void part(int[] a, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        part(a, lo, mid);
        part(a, mid + 1, hi);
        for (int i = lo; i <= mid; i++) {
            a[i] = 2 * a[i] - 1;
        } 
        for (int i = mid + 1; i <= hi; i++) {
            a[i] = 2 * a[i];
        }
        return;
    }
}

复杂度分析

• 时间复杂度：O(N)，其中 N 为数组长度。
• 空间复杂度：O(1)

[Hacker90]

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; };

[callmeerika]

思路

分治

代码

var beautifulArray = function(n) {
    let memo = new Map();
    const f = (n) => {
         if (memo.has(n)) {
             return memo.get(n);
         }
         let ans = new Array(n);
         if (n === 1) {
             ans[0] = 1;
         } else {
             let t = 0;
             let l = f(Math.ceil(n/2));
             l.forEach(v => ans[t++] = 2*v - 1);
             let r = f(Math.floor(n/2));
             r.forEach(v => ans[t++] = 2*v);
         }
         memo.set(n, ans)
         return ans;
    }
    return f(n)
};

复杂度

时间复杂度：O(nlogn)
空间复杂度：O(nlogn)

[honeymeng-hub]

class Solution { Map<Integer, int[]> memo = new HashMap(); public int[] beautifulArray(int n) { memo.put(1, new int[]{1}); return dp(n); } private int[] dp(int n) { if (memo.get(n) != null) { return memo.get(n); } int[] res = new int[n]; int i = 0; for (int x : dp((n + 1) / 2)) { res[i++] = 2 x - 1; } for (int x : dp(n / 2)) { res[i++] = 2 x; } memo.put(n, res); return res; } }

[hdyhdy]

func beautifulArray(n int) []int {
    if n == 1 {
        return []int{1}
    }

    array := make([]int, 0, n)

    odds := beautifulArray((n+1)>>1)
    evens := beautifulArray(n>>1)

    for _, o := range odds {
        array = append(array, 2*o-1)
    }

    for _, e := range evens {
        array = append(array, 2*e)
    }

    return array
}

[shamworld]

var beautifulArray = function(n) {
    let map=new Map()
    const f=(n)=>{
         if (map.has(n)) {
             return map.get(n)
         }
         let ans=new Array(n)
         if (n==1) {
             ans[0]=1
         }else{
             let t=0
             let l=f(Math.ceil(n/2)) 
             l.forEach((v)=>ans[t++]=2*v-1)
             let r=f(Math.floor(n/2)) 
             r.forEach((v)=>ans[t++]=2*v)
         }
         map.set(n,ans)
         return ans
    }
    return f(n)
};

[demo410]

 public int[] beautifulArray(int N) {
        int[] a = new int[N];
        Arrays.fill(a, 1);
        part(a, 0, N - 1);
        return a;
    }
    public void part(int[] a, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        part(a, lo, mid);
        part(a, mid + 1, hi);
        for (int i = lo; i <= mid; i++) {
            a[i] = 2 * a[i] - 1;
        } 
        for (int i = mid + 1; i <= hi; i++) {
            a[i] = 2 * a[i];
        }
        return;
    }

[ChenJingjing85]

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

[fornobugworld]

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

[taojin1992]

/*
nums[i] + nums[j] = odd

i < j

one from even part, one from odd part

after linear transformation, still beautiful 

grow the larger one from the smaller beautiful array

n = 1,[1], odd, next time to even, (2*x)
n = 2, [1,  2]  -> even , next round, transform to odd (2*x-1)
n = 3, from build((3+1)/2), build(3/2), namely, build(2), build(1)
[1,2,3]

1*2
1*2-1, 2*2-1
[2,1,3] 

or
1*2 - 1
1*2, 2*2
1,2,4-> not permutation of [1,n], won't work

n=4
[1,2]
previously even-> odd, previously odd -> even
1,3,2,4, works

or
previously odd -> even, previously even -> odd
2,4,1,3, works

Time:
O(logn) levels, each O(n)

O(nlogn)

Space:O(n) for the map and output array
stack: O(logn)

O(n+logn)= O(n)
*/

class Solution {
    Map<Integer, int[]> cache = new HashMap<>();

    public int[] beautifulArray(int n) {
        cache.put(1, new int[]{1});
        return build(n);
    }

    private int[] build(int n) {
        if (cache.containsKey(n)) {
            return cache.get(n);
        }
        int[] res = new int[n];
        int[] shorter = build(n/2); // shorter or equal size compared to the other one, range [1,n/2] -> [2,n] even's
        int[] longer = build(n - n/2);   // range [1,n-n/2], -> odd's [1, n-1]

        // linearly transform potentially longer to odd, 2*x - 1
        // shorter to even
        // either equal size or one longer by 1
        // [1,2,3],[1,2]
        for (int i = 0; i < longer.length; i++) {
            res[i] = 2 * longer[i] - 1;
        }

        for (int i = 0; i < shorter.length; i++) {
            res[i + longer.length] = 2 * shorter[i];
        }
        // odd, even append, we can swap these two for loops
        cache.put(n, res);

        return res;
    }
}

[zzzpppy]

class Solution {
    Map<Integer,int[]> map;
    public int[] beautifulArray(int n) {
        map = new HashMap<>();
        map.put(1,new int[]{1});
        return f(n);}
        private int[] f(int N){
        if(!map.containsKey(N)){
            int index = 0;
            int[] res = new int[N];
            for(int x : f((N + 1) / 2)){
                res[index++] = 2 * x - 1;
            }
            for(int x : f(N / 2)){
                res[index++] = 2 * x;
            }
            map.put(N, res);
        }
        return map.get(N);
    }  
}

[hx-code]

var beautifulArray = function(n) { let map=new Map() const f=(n)=>{ if (map.has(n)) { return map.get(n) } let ans=new Array(n) if (n==1) { ans[0]=1 }else{ let t=0 let l=f(Math.ceil(n/2)) l.forEach((v)=>ans[t++]=2v-1) let r=f(Math.floor(n/2)) r.forEach((v)=>ans[t++]=2v) } map.set(n,ans) return ans } return f(n)

[machuangmr]

代码

class Solution {
    Map<Integer, int[]> memo;
    public int[] beautifulArray(int N) {
        memo = new HashMap<>();
        memo.put(1, new int[]{1});
        return f(N);
    }

    private int[] f(int N){
        if(!memo.containsKey(N)){
            int index = 0;
            int[] res = new int[N];
            for(int x : f((N + 1) / 2)){
                res[index++] = 2 * x - 1;
            }
            for(int x : f(N / 2)){
                res[index++] = 2 * x;
            }
            memo.put(N, res);
        }
        return memo.get(N);
    }
}

[Richard-LYF]

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