【Day 70 】2023-04-24 - 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

 

[JasonQiu]

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

Time: O(nlogn) Space: O(n)

[kofzhang]

思路

分治

复杂度

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

代码

class Solution:
    def beautifulArray(self, n: int) -> List[int]:

        def helper(n):
            res = []
            if n!=1:
                for x in helper((n+1)//2):
                    res.append(2*x-1)
                for x in helper(n//2):
                    res.append(2*x)
            else:
                res.append(1)
            return res

        return helper(n)

[LIMBO42]

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

[NorthSeacoder]

/**
 * @param {number} n
 * @return {number[]}
 */
var beautifulArray = function (n) {
    const map = new Map();
    map.set(1, [1])
    const build = (n) => {
        if (map.has(n)) return map.get(n);
        //左奇,右偶
        const left = build((n + 1) >> 1).map(v => 2 * v - 1)//奇数侧
        const right = build(n >> 1).map(v => 2 * v)//偶数侧;
        const res = [...left, ...right];
        map.set(n, res);
        return res
    }
    return build(n)
};

[bookyue]

TC: O(nlogn)
SC: O(logn)

    public int[] beautifulArray(int n) {
        int[] arr = new int[n];
        Arrays.fill(arr, 1);
        part(arr, 0, n - 1);
        return arr;
    }

    private void part(int[] arr, int lo, int hi) {
        if (lo >= hi) return;

        int mid = (lo + hi) >>> 1;
        part(arr, lo, mid);
        part(arr, mid + 1, hi);

        for (int i = lo; i <= mid; i++)
            arr[i] = arr[i] * 2 - 1;

        for (int i = mid + 1; i <= hi; i++)
            arr[i] = arr[i] * 2;
    }

[aoxiangw]

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 += [a * 2 - 1]
            for b in dp(n // 2):
                ans += [b * 2]
            return ans

        return dp(n)

O(nlogn), O(n + logn)

[chanceyliu]

代码

function beautifulArray(n: number): number[] {
  if (n === 1) return [1];
  return [
    ...beautifulArray(Math.ceil(n / 2)).map((i) => 2 * i - 1),
    ...beautifulArray(Math.floor(n / 2)).map((i) => 2 * i),
  ];
}

[Abby-xu]

class Solution:
    def beautifulArray(self, n: int) -> List[int]:
        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]

[RestlessBreeze]

code

class Solution {
public:
    vector<int> bea(int n)
    {
        vector<int> ans(n, 0);
        if (n != 1)
        {
            int t = 0;
            for (auto x : bea((n + 1) / 2))
                ans[t++] = 2 * x - 1;
            for (auto x : bea(n / 2))
                ans[t++] = 2 * x;
        }
        else
            ans[0] = 1;
        return ans;
    }

    vector<int> beautifulArray(int n) {
        return bea(n);
    }
};

[jackgaoyuan]

func beautifulArray(n int) []int {
    var res = make([]int,n)
    for i := 0;i<len(res);i++{
        res[i]= 1
    }
    part(res,0,n-1)
    return res
}

func part(arr []int,lo int,hi int){
    if hi<=lo{
        return
    }
    mid := (lo+hi)/2
    part(arr,lo,mid)
    part(arr,mid+1,hi)
    for i := lo;i<=mid;i++{
        arr[i] = 2 * arr[i] -1
    }
    for i := mid+1;i<=hi;i++{
        arr[i] = 2 *arr[i]
    }
    return
}

[snmyj]

class Solution(object):
    def beautifulArray(self, N):
        """
        :type N: int
        :rtype: List[int]
        """

        l = 1
        now = [1]
        while l < N:
            now = [x + x - 1 for x in now] + [x + x for x in now]
            l += l

        res = []
        for num in now:
            if num <= N:
                res.append(num)

        return res

[Meisgithub]

class Solution {
public:
    vector<int> beautifulArray(int n) {
        vector<int> ans;
        if(n==1){
            ans.push_back(1);
            return ans;
        }
        int odd=(n+1)/2;
        int even=n/2;
        vector<int> left=beautifulArray(odd);
        vector<int> right=beautifulArray(even);
        for(auto &val:left){
            ans.push_back(val*2-1);
        }
        for(auto &val:right){
            ans.push_back(val*2);
        }
        return ans;
    }

};

[61hhh]

class Solution {
    public int[] beautifulArray(int n) {
        List<Integer> res = new ArrayList<>();
        res.add(1); // 长度为1的漂亮数组是 [1]
        while (res.size() < n) {
            List<Integer> tmp = new ArrayList<>();
            for (int i : res) {
                if (i * 2 - 1 <= n) { // 将奇数乘以2后减去1，判断是否小于等于n
                    tmp.add(i * 2 - 1);
                }
            }
            for (int i : res) {
                if (i * 2 <= n) { // 将偶数乘以2，判断是否小于等于n
                    tmp.add(i * 2);
                }
            }
            res = tmp; // 更新res
        }
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            ans[i] = res.get(i);
        }
        return ans;
    }
}

复杂度分析

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

[FireHaoSky]

思路：分治算法，分列奇偶列表

代码：python

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)

复杂度分析

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

[harperz24]

class Solution:
    def beautifulArray(self, n: int) -> List[int]:
        memo = {}
        return self.divide(n, memo)

    def divide(self, n, memo):
        if n in memo:
            return memo[n]        
        if n == 1:
            return [1]

        odds = self.divide((n + 1) // 2, memo)
        evens = self.divide(n // 2, memo)

        left = [2*x-1 for x in odds]
        right = [2*x for x in evens]

        memo[n] =  left + right
        return left + right

        # divide
        # time: (n logn)
        # space: (n logn)

[GuitarYs]

class Solution:
    def beautifulArray(self, n: int) -> List[int]:
        memo = {}
        return self.divide(n, memo)

    def divide(self, n, memo):
        if n in memo:
            return memo[n]        
        if n == 1:
            return [1]

        odds = self.divide((n + 1) // 2, memo)
        evens = self.divide(n // 2, memo)

        left = [2*x-1 for x in odds]
        right = [2*x for x in evens]

        memo[n] =  left + right
        return left + right

        # divide
        # time: (n logn)
        # space: (n logn)

[wangqianqian202301]

class Solution:
    def beautifulArray(self, n: int) -> List[int]:
        nums = list(range(1, n+1))
        def ba(arr, count):
            if count < 3:
                return arr
            odd = arr[1::2]
            even = arr[0::2]
            return ba(odd, len(odd)) + ba(even, len(even))
        return ba(nums, n)

[Diana21170648]

思路

分治，分为偶数和奇数，再合到一起，奇数=偶数，或者奇数数量比偶数多一个

from typing import List
2   class Solution:
3       def beautifulArray(self, N: int) -> List[int]:
4         
5           def dp(n):
6               if n == 1:
7                   return [1]
8               ans = []
9               # [1,n] 中奇数比偶数多1或一样
10              for a in dp(n - n // 2):
11                  ans += [a * 2 - 1]
12              for b in dp(n // 2):
13                  ans += [b * 2]
14              return ans
15  
16          return dp(N)
17  Solution().beautifulArray(5)

**复杂度分析**
- 时间复杂度：O(nlogn)，有排序。
- 空间复杂度：O(n+logn)

[zhangyu1131]

class Solution {
public:
    vector<int> beautifulArray(int n) {
        // 数学性质，挺难想的，记录一下吧
        // 如果[i, j, k]是漂亮数组，那么[t*i + b, t*j + b, t * k +b]也是漂亮数组
        vector<vector<int>> dp(n + 1, vector<int>());
        dp[1] = {1};
        for (int i = 2; i <= n; ++i)
        {
            int left_num = (i + 1) / 2;
            int right_num = i / 2;
            for (auto num : dp[left_num])
            {
                dp[i].push_back(2 * num - 1);
            }
            for (auto num : dp[right_num])
            {
                dp[i].push_back(2 * num);
            }
        }

        return dp[n];
    }
};

[kangliqi1]

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

[X1AOX1A]

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)

[Fuku-L]

代码

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)){
                ans[t++] = 2*x-1;
            } 
            for(int x:f(n/2)){
                ans[t++] = 2*x;
            }
        }
        memo.put(n, ans);
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(nlogn)，f(n)调用logn次，每次时间消耗O(n)。
• 空间复杂度：O(nlogn)，f(n)调用logn次，形成大小为logn的递归栈，每次需要存储长度为n的数组空间。

[tzuikuo]

思路

分治

代码

class Solution {
public:
    vector<int> beautifulArray(int n) {
        return solve(n);
    }

    vector<int> solve(int n){
        //base case
        if(n==1) {
            vector<int> k = {1};
            return k;
        }

        vector<int> ans = solve(n-1);
        vector<int> temp;
        for(int i = 0; i < ans.size(); i++){
            if(2*ans[i]-1 <= n) temp.push_back(2*ans[i]-1);
        }
        for(int i = 0; i < ans.size(); i++){
            if(2*ans[i] <= n) temp.push_back(2*ans[i]);
        }
        return temp;
    }
};

复杂度分析 -待定

[Lydia61]

932. 漂亮数组

思路

哈希表

代码

class Solution {
public:
    unordered_map<int,vector<int>> mp;
    vector<int> beautifulArray(int n) {
        vector<int> ans;
        if(n==1){
            ans.push_back(1);
            return ans;
        }
        if(mp.count(n)){
            return mp[n];
        }
        int odd_num=(n+1)/2;
        int even_num=n/2;
        vector<int> left_arry=beautifulArray(odd_num);
        vector<int> right_arry=beautifulArray(even_num);
        //将左侧数组映射为奇数
        for(auto &val:left_arry){
            ans.push_back(val*2-1);
        }
        //将右侧数组映射为偶数
        for(auto &val:right_arry){
            ans.push_back(val*2);
        }
        mp[n]=ans;
        return ans;
    }

};

复杂度分析

• 时间复杂度：O(n^2)
• 空间复杂度：O(n)

[Jetery]

class Solution {
public:
    unordered_map<int,vector<int>> mp;
    vector<int> beautifulArray(int n) {
        vector<int> ans;
        if(n == 1){
            ans.push_back(1);
            return ans;
        }
        if(mp.count(n)) return mp[n];

        int odd = (n + 1) / 2;
        int even = n / 2;
        vector<int> left = beautifulArray(odd);
        vector<int> right = beautifulArray(even);

        for(auto &val : left){
            ans.push_back(val * 2 - 1);
        }

        for(auto &val : right){
            ans.push_back(val * 2);
        }
        mp[n] = ans;
        return ans;
    }

};

[Hughlin07]

class Solution {

public int[] beautifulArray(int n) {
    int[] ans = new int[n];
    for(int i = 0; i  < n; i++){
        ans[i] = i+1;
    }
    recursion(ans, 0, n-1);
    return ans;
}

public void recursion(int[] arr, int left, int right){
    if(left >= right)
        return;
    ArrayList<Integer> l = new ArrayList<>();
    ArrayList<Integer> r = new ArrayList<>();

    boolean alt = true

    for(int i = left; i <= right; i++){ 
        if(alt)
            l.add(arr[i]);
        else
            r.add(arr[i]);
        alt = !alt;
    }

    for(int i = left; i <= right; i++){ 
        if(!l.isEmpty())
            arr[i] = l.remove(0);
        else
            arr[i] = r.remove(0);
    }
    recursion(arr, left, (right+left)/2);
    recursion(arr, (left+right)/2+1, right);
}

}

[sye9286]

代码

var beautifulArray = function (n) {
  const map = new Map();
  map.set(1, [1]); 
  const recursion = (n) => {
    if (map.has(n)) return map.get(n);
    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);
};

[joemonkeylee]

思路

没做出来。

代码

        public int[] BeautifulArray(int n)
        {
            int[] arr = new int[n];
            Array.Fill(arr, 1);
            Recursive(arr, 0, n - 1);
            return arr;
        }

        private void Recursive(int[] arr, int min, int max)
        {
            if (max <= min) return;
            int mid = min + (max - min) / 2;
            Recursive(arr, min, mid);
            Recursive(arr, mid + 1, max);
            for (int i = min; i <= mid; i++)
            {
                arr[i] = 2 * arr[i] - 1;
            }
            for (int i = mid + 1; i <= max; i++)
            {
                arr[i] = 2 * arr[i];
            }
            return;
        }

[Zoeyzyzyzy]

class Solution {
    // 2 * y != x + z; 2*y 是偶数，要想不等于只能是偶数+奇数 -> 奇数
    // 如果一个数组是漂亮数组，那么各元素线性变换后也是漂亮数组
    // eg: 同*：(2 * y) * a != x * a + z * a = > (x + z) * a
    // 同+:  2 * (y + a) = 2 * y + 2 * a != x + a + z + a
    // 线性变换： k * (2 * y) + b = 2*k*y + b ! = k *(x+z) + b
    // f(n) 可以由之前的一系列变换而来
    // N = 1 时有[1] , N = 2 时 通过N = 1 变换 1*2 -1 = 1 ， 1 *2 =2
    // N = 3 时, 通过N = 2 和 N = 1 变换得到， N = 2 变换得到奇数部分 2 * 1 - 1 = 1， 2*2 - 1 = 3, N = 1 变换得到偶数部分：2 * 1 = 2 => [1,3,2]
    // Time Complexity: O(nlogn) f(n) 调用logn次，每次消耗O（n): Space Complexity: O(nlogn) f(n)调用logn次形成大小为logn的递归栈，每次需要长度为n的数组存储结果
    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);
    }
}

[lp1506947671]

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)

复杂度分析

令 n 为数组长度。

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