【Day 70 】2023-01-09 - 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

 

[zjsuper]

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)

[yuxiangdev]

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)

[guowei0223]

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)

[buer1121]

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

本来第一开始想到的也是分治法

    #但是想到的是LC439翻转对那种题
    #本题还是有很强的技巧性，仿射变换
    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)

[JancerWu]

思路

1. 从条件入手，得出前面排奇数，后面排偶数，因为奇数+偶数≠偶数
2. 推导漂亮数组线性变换后仍是漂亮数组
3. 分治，先排前面的奇数(线性转换)，再排后面的偶数(线性转换)
4. 递归漂亮数组时记忆化搜索去重

代码

class Solution {
    Map<Integer, int[]> memory = new HashMap<>();
    public int[] beautifulArray(int n) {
        memory.put(1, new int[]{1});
        return f(n);
    }
    public int[] f(int n) {
        if (memory.containsKey(n)) return memory.get(n);
        int[] ans = new int[n];
        int id = 0, oddCnt = (n + 1) / 2, evenCnt = n / 2;
        for (int num : f(oddCnt)) {
            ans[id++] = num * 2 - 1;
        }
        for (int num : f(evenCnt)) {
            ans[id++] = num * 2;
        }
        memory.put(n, ans);
        return ans;
    }
}

[ringo1597]

代码

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

[bookyue]

code

    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 (hi <= lo) return;

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

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

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

[snmyj]

class Solution {
public:
    vector<int> beautifulArray(int n) {
       if(n==1) return {1};
       vector<int> res;
       vector<int> s1=beautifulArray((n+1)/2);
       vector<int> s2=beautifulArray(n/2);
       for(auto x:s1) res.push_back(x+x-1);
       for(auto x:s2) res.push_back(x+x);
       return res;
    }
};

[Abby-xu]

思路

奇加偶才能满足条件，最后需要确保长度是n

代码

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]

复杂度

。。。

[jackgaoyuan]

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
}

[A-pricity]

/**
 * @param {number} n
 * @return {number[]}
 */
/**
 * @param {number} n
 * @return {number[]}
 */
var beautifulArray = function(n) {
    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)];
};

[Elsa-zhang]

# 932. 漂亮数组
''' 分治 nlogn
'''

class Solution:
    def beautifulArray(self, n: int) -> list[int]:
        def dp(n):
            if n == 1:
                return [1]
            ans = []
            for a in dp((n+1)//2):
                ans += [a * 2 - 1]
            for b in dp(n//2):
                ans += [b * 2]
            return ans

        return dp(n)

n = 4
solution = Solution()
ans = solution.beautifulArray(n)
print(ans)

[paopaohua]

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

[klspta]

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

    }
}

[RestlessBreeze]

code

class Solution {
public:
    unordered_map<int,vector<int> > mp;
    vector<int> beautifulArray(int N) {
        return f(N);
    }
    vector<int> f(int N) {
        vector<int> ans(N, 0);
        int t = 0;
        if (mp.find(N) != mp.end()) {
            return mp[N];
        }
        if (N != 1) {
            for (auto x : f((N+1)/2)){
                ans[t++]= 2 * x - 1;
            } 
            for (auto x : f(N/2)){
                ans[t++] =  2 * x;
            }
        }else {
            ans[0] = 1;
        }
        mp[N] = ans;
        return ans;
    }
};

[mayloveless]

思路

参考官方解答.从最小扩展到最大

代码

/**
 * @param {number} n
 * @return {number[]}
 */
var 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)

[tiandao043]

思路

看了题解，分治，一半奇数一半偶数，难点在于想明白性质。

代码

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

O(nlogn) O(n + logn)

[BruceZhang-utf-8]

代码

• 语言支持：Java

Java Code:

class Solution {
    private void solve(int[] num, int begin, int end, int[] temp) {
        if (end - begin <= 2) {
            return;
        }
        int pos = (end - begin + 1) >> 1;
        for (int i = begin; i < end; i += 2) {
            temp[begin + ((i - begin) >> 1)] = num[i];
            if (i < end - 1) {
                temp[begin + pos + ((i - begin) >> 1)] = num[i + 1];
            }
        }
        for (int i = begin; i < end; i++) {
            num[i] = temp[i];
        }
        solve(num, begin, begin + pos, temp);
        solve(num, begin + pos, end, temp);
    }

    public int[] beautifulArray(int N) {
        int[] num = new int[N], temp = new int[N];
        for (int i = 0; i < N; i++) {
            num[i] = i + 1;
        }
        if (N <= 2) {
            return num;
        }
        solve(num, 0, N, temp);
        return num;
    }
}

[Jetery]

代码 (cpp)

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

};

[whoam-challenge]

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)

[FlipN9]

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

    1. A[k] * 2 必为偶数, 一个简单的办法是 令 A[i] + A[j] 一个为奇数, 一个为偶数
       A[i] 来自 left 部分 (都为奇数)       A[j] 来自 right 部分 (都为偶数)

    2. 如果 A 是一个漂亮数组 将 A 中的每一个数 x 进行 kx + b (k > 0) 的映射，其仍然为漂亮数组,
       这样可以通过一个漂亮数组, 衍生出 为奇数 的漂亮数组 和 为偶数 的漂亮数组

    所以, 我们可以就
       在 [1..N] 中有 (N+1)/2 个奇数和 N/2 个偶数, 
       通过 f((n+1)/2) 中每个元素进行 *2-1 映射到 f(n) 中的 (n+1)/2 个奇数元素构成的漂亮数组
       通过 f((n)/2)   中每个元素进行 *2   映射到 f(n) 中的 (n)/2   个偶数元素构成的漂亮数组

       而对于 A[k]*2 != A[i]+A[j]， 当对 A[k], A[i], A[j] 同时乘以2, 并同时-1，并不影响不等号。

       N =  10  [1, 9, 5, 3, 7, 2, 10, 6, 4, 8]
            5   [1, 5, 3, 2, 4]
            3   [1, 3, 2]
            2   [1, 2]
            1   [1]

       TC: O(NlogN)     SC: O(NlogN)
*/

class Solution {
    Map<Integer, int[]> memo;

    public int[] beautifulArray(int N) {
        memo = new HashMap<>();
        memo.put(1, new int[] {1}); // base case
        return dp(N);
    }

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

        int[] res = new int[N];
        // 如果n不为1，需要在 前(n+1)/2个位置放奇数 后(n)/2个位置放偶数                   
        int i = 0;
        for (int x : dp( (N+1)/2 ))      // n个数中有 (n+1)/2 奇数
             res[i++] = 2 * x - 1;  
        for (int x : dp( N/2 ))          //n个数中有 (n)/2 个偶数
             res[i++] = 2 * x;

        memo.put(N, res);
        return res;
    }
}