Open azl397985856 opened 2 years ago
JiangWenqi
commented
2 years ago class Solution
{
public:
vector<int> beautifulArray(int n)
{
if (n == 1)
return {1};
vector<int> left = beautifulArray((n + 1) / 2), right = beautifulArray(n / 2);
vector<int> res;
for (int &x : left)
res.push_back(2 * x - 1);
for (int &y : right)
res.push_back(2 * y);
return res;
}
};
MichaelXi3
commented
2 years ago 分治奇偶
class Solution {
public int[] beautifulArray(int N) {
int[] res = new int[N];
if (N == 1) {
return new int[] {1};
} else if (N == 2) {
return new int[] {1, 2};
} else {
int[] odds = beautifulArray((N + 1) / 2);
int[] even = beautifulArray(N / 2);
for (int i = 0; i < odds.length; i ++) {
res[i] = odds[i] * 2 - 1;
}
for (int j = 0; j < even.length; j ++) {
res[odds.length + j] = even[j] * 2;
}
}
return res;
}
}
asuka1h
commented
2 years ago class Solution { fun beautifulArray(n: Int): IntArray {
if(n == 1){
return intArrayOf(1)
}
// val ret:MutableList<Int> = MutableList()
var left = beautifulArray((n+1)/2)
var right = beautifulArray(n/2)
val ret: MutableList<Int> = mutableListOf()
// val ret:MutableList<Int> = IntArray()
for(i in left){
ret.add(i*2 -1)
}
for(i in right){
ret.add(i*2)
}
return ret.toIntArray()
}}
ghost
commented
2 years ago class Solution:
def beautifulArray(self, n: int) -> List[int]:
res = [1]
while(len(res) < n):
t = []
for i in res:
if i*2-1 <= n:
t.append(i*2-1)
for i in res:
if i*2 <= n:
t.append(i*2)
res = t
return res
MoonLee001
commented
2 years ago var beautifulArray = function(N) {
const memo = new Map();
const f = (n) => {
if (memo.has(n)) {
return memo.get(n);
}
let ans = [];
if (n == 1) {
ans[0] = 1;
} else {
let t = 0;
let l = f(Math.ceil(n / 2));
l.forEach((v) => {
return ans[t++] = 2 * v - 1;
});
let r = f(Math.floor(n / 2));
r.forEach((v) => {
return ans[t++] = 2 * v;
})
}
memo.set(n, ans);
return ans;
}
return f(N);
};
djd28176
commented
2 years ago
class Solution {
public int[] beautifulArray(int n){
ArrayList<Integer> res = new ArrayList<>();
res.add(1);
while(res.size() < n){
ArrayList<Integer> tmp = new ArrayList<>();
for(int odd : res){
if(odd*2 -1 <=n){
tmp.add(odd*2 - 1);
}
}
for(int even : res){
if(even * 2<=n) {
tmp.add(even*2);
}
}
res = tmp;
}
return res.stream().mapToInt(i -> i).toArray();
}
}
houmk1212
commented
2 years ago 没做出来，参考了答案
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;
}
}
ha0cheng
commented
2 years ago 没做出来，参考答案 思路：分治法构造，奇偶分析 首先漂亮数组有两个性质： 1.线性变换ax+b后仍是漂亮数组 因为2a=b+c，线性变换后等号不变 2.AB是奇偶性不同的漂亮数组，那么拼接A和B，仍是一个漂亮数组。 这是因为2a=b+c中，需要保证b+c为偶数，所以b和c不可能分别从A和B中取出，只能从其中一个取，而a又夹在b,c中间，于是只要A，B为漂亮数组，不存在这样的a,b,c，那么A+B即是漂亮数组。
分治法，将n个数的数组，分治成偶数数组A，大小为n//2，然后构造n//2的完美数组，乘2就是该偶数数组A。奇数数组B，大小为n-n//2, 构造n-n//2的完美数组，每个数*2-1即是该奇数数组。这样通过分治法，可以将一个大小为n的完美数组分成大小为n//2和n-n//2的两个小数组，从而用递归解决。
改进一点：递归时如果n是偶数，那么n-n//2=n//2，只需一次递归即可.
复杂度分析： 时间复杂度：O(nlogn), 总共递归次数为logn，每次需要运算n次 空间复杂度：O(logn+n), 递归栈深度为logn, 每次栈里调用也需要开辟n大小的空间来存储
class Solution:
def beautifulArray(self, n: int) -> List[int]:
def dp(n):
if n==1:
return [1]
r = []
X = dp(n//2)
for i in X:
r.append(i*2)
if n%2==0:
for i in X:
r.append(2*i-1)
else:
for i in dp(n-n//2):
r.append(2*i-1)
return r
return dp(n)
ShawYuan97
commented
2 years ago Python3 Code:
class Solution:
def beautifulArray(self, n: int) -> List[int]:
"""
不存在k，满足i<k<j，使得A[k] * 2 = A[i] + A[j]
"""
@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)
复杂度分析
令 n 为数组长度。
hyh331
commented
2 years ago 分治思想，奇+偶=奇，若要A[k]*2=A[I]+A[J]不成立的话，把N分为两部分，一部分为奇数，一部分为偶数，则此式一定不成立。
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;
}
};
ZacheryCao
commented
2 years ago 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)
currybeefer
commented
2 years ago vector
return res;
}
xil324
commented
2 years ago class Solution(object):
def beautifulArray(self, n):
"""
:type n: int
:rtype: List[int]
"""
self.memo = {1:[1]};
return self.helper(n)
def helper(self, n):
if n not in self.memo:
odd = self.helper((n+1)//2);
even = self.helper(n//2);
self.memo[n] = [2*i-1 for i in odd] + [2*i for i in even];
return self.memo[n]time complexity: O(nlogn)
Geek-LX
commented
2 years ago 思路：分治
代码：
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 为数组长度。
Ellie-Wu05
commented
2 years ago 参考了答案
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)
xingchen77
commented
2 years ago 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)
flyzenr
commented
2 years ago -
class Solution:
def beautifulArray(self, N: int) -> List[int]:
# 哈希表记忆，key记录数组大小，value记录漂亮数组
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)
miss1
commented
2 years ago 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;
};
L-SUI
commented
2 years ago
/**
* @param {number} n
* @return {number[]}
*/
/**
* @param {number} N
* @return {number[]}
*/
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)
};
zhishinaigai
commented
2 years ago 数学不太行，下一个
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;
}
};
LQyt2012
commented
2 years ago 分治，left存储奇数并且做奇数的线性变换，right存储偶数并且做偶数的线性变换。
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)func beautifulArray(n int) []int {
memo := map[int][]int{}
memo[1] = []int{1}
return dfs(memo, n)
}
func dfs(memo map[int][]int, n int) []int {
if _, ok := memo[n]; ok {
return memo[n]
}
left := make([]int, 0)
right := make([]int, 0)
for _, val := range dfs(memo, (n+1)/2) {
left = append(left, 2*val-1)
}
for _, val := range dfs(memo, n/2) {
right = append(right, 2*val)
}
memo[n] = append(left, right...)
return memo[n]
}时间复杂度：O(NlogN)
空间复杂度：O(NlogN)
EldinZhou
commented
2 years ago
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)
yangyuhuan
commented
2 years ago 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++]=2v-1)
let r=f(Math.floor(n/2))
r.forEach((v)=>ans[t++]=2v)
}
memo.set(n,ans)
return ans
}
return f(N)
};
wychmod
commented
2 years ago 主要是对题意理解的问题，如果能知道左边是奇数右边是偶数就是漂亮数组，那么不断的往外延伸就行，主要是可能跟数学有关，我不太行。
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)
xiayuhui231
commented
2 years ago 漂亮数组
class Solution {
public:
vector<int> beautifulArray(int N) {
vector<int> vec;
if(1 == N)
{
vec.push_back(1);
return vec;
}
else
{
vector<int> vTemp1 = beautifulArray((N+1)/2);
for(int i = 0;i<vTemp1.size();i++)
vec.push_back(vTemp1[i]*2-1);
vector<int> vTemp2 = beautifulArray(N/2);
for(int i = 0;i<vTemp2.size();i++)
vec.push_back(vTemp2[i]*2);
}
return vec;
}
};
tensorstart
commented
2 years ago var beautifulArray = function (n) {
const map = new Map();
map.set(1, [1]); // 基础值
const recursion = (n) => {
// 如果已经保存过了，直接取漂亮数组
if (map.has(n)) return map.get(n);
// n 的奇偶不定，所以奇数向上取整，即 n===5 时，奇数有 5+1 >> 1 个，偶数只有 5>>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);
};
freedom0123
commented
2 years ago class Solution {
public int[] beautifulArray(int n) {
int[] res = new int[n];
for(int i = 0; i < n; i++) {
res[i] = i + 1;
}
helper(res, 0, n - 1);
return res;
}
private void helper(int[] a, int l, int r) {
if(l == r || l + 1 == r) { return; }
int[] tmp = new int[r - l + 1];
int k = 0, mid = l + r >> 1;
for(int i = l; i <= r; i += 2) {
tmp[k++] = a[i];
}
for(int i = l + 1; i <= r; i += 2) {
tmp[k++] = a[i];
}
for(int i = l, j = 0; i <= r; i++, j++) {
a[i] = tmp[j];
}
helper(a, l, mid);
helper(a, mid + 1, r);
}
}
carterrr
commented
2 years ago class Solution { public int[] beautifulArray(int n) { // 奇数 + 偶数 = 奇数 不可能等于偶数 因此 把n分为 前半部分奇数 后半部分偶数 奇数部分 = n+1)/2 部分的奇数 2 -1 推导得到 偶数部分 n/2 部分 2 得到 奇数部分 偶数部分都是漂亮数组 正向计算 会算一堆无关数据 可以考虑反向递归 Map<Integer, int[]> map = new HashMap<>(); map.put(1, new int[]{1});
for(int i = 2; i <= n; i++) {
int[] tmp = new int[i];
int[] left = map.get((i + 1)/2);
int[] right = map.get(i / 2);
int j = 0;
for(int l : left) {
tmp[j++] = l * 2 - 1;
}
for(int r : right) {
tmp[j++] = r * 2;
}
map.put(i, tmp);
}
return map.get(n);
}}
TonyLee017
commented
2 years ago 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)
revisegoal
commented
2 years ago 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;
}
}
taojin1992
commented
2 years ago /*
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;
}
}
maggiexie00
commented
2 years ago def recurse(self, nums):
if len(nums) <= 2: return nums
return self.recurse(nums[::2]) + self.recurse(nums[1::2])
def beautifulArray(self, n: int) -> List[int]:
return self.recurse([i for i in range(1, n+1)])
sallyrubyjade
commented
2 years ago /**
* @param {number} n
* @return {number[]}
*/
var beautifulArray = function(n) {
let map = new Map();
let 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);
};
XXjo
commented
2 years ago var beautifulArray = function(n) {
let map = new Map(); //以n为key，漂亮数组为value
map.set(1, [1]);
var f = function(n){
if(map.get(n)) return map.get(n);
let odds = f((n + 1) >> 1).map(i => 2 * i - 1);
let evens = f(n >> 1).map(i => 2 * i);
map.set(n, [...odds, ...evens]);
return map.get(n);
}
return f(n);
};
houyanlu
commented
2 years ago 最关键：A是一个奇数构成的漂亮数组，B是一个偶数构成的漂亮数组，那么A+B也是一个漂亮数组 比如:{1,5,3,7}+{2,6,4,8}={1,5,3,7,2,6,4,8}也是一个漂亮数组。
class Solution {
public:
unordered_map<int, vector<int>> map;
vector<int> beautifulArray(int n) {
vector<int> res;
if (n == 1) {
res.push_back(1);
return res;
}
if (map.find(n) != map.end()) {
return map[n];
}
// 奇数和偶数的个数
int odd = (n + 1) / 2;
int even = n / 2;
vector<int> left = beautifulArray(odd);
vector<int> right = beautifulArray(even);
for (auto x : left) {
res.push_back(2 * x - 1); // 奇数
}
for (auto x : right) {
res.push_back(2 * x); // 偶数
}
// 记忆
map[n] = res;
return res;
}
};
复杂度分析
Yongxi-Zhou
commented
2 years ago divide and conquer
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)time O(nlogn) space O(nlogn)
932. 漂亮数组
入选理由
暂无
题目地址
https://leetcode-cn.com/problems/beautiful-array/
前置知识
题目描述
对于每个 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