class Solution {
public:
vector<int> beautifulArray(int n) {
}
};
932. 漂亮数组
对于某些固定的 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
原站题解
golang 解法, 执行用时: 8 ms, 内存消耗: 9.3 MB, 提交时间: 2022-11-27 13:04:51
func beautifulArray(n int) []int {
dp := make([][]int, n+1)
for i:=1; i<=n; i++ {
dp[i] = make([]int, 0, i)
if i == 1 {
dp[i] = append(dp[i], 1)
continue
}
l, r := (i+1)>>1, i>>1
for j := range dp[l] {
dp[i] = append(dp[i], 2*dp[l][j]-1)
}
for k := range dp[r] {
dp[i] = append(dp[i], 2*dp[r][k])
}
}
return dp[n]
}
golang 解法, 执行用时: 0 ms, 内存消耗: 3.1 MB, 提交时间: 2022-11-27 13:04:31
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
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2.3 MB, 提交时间: 2022-11-27 13:04:05
// 如果A是一个漂亮数组，那么2*A+b是一个漂亮数组
// 如果A是一个奇数漂亮数组，B是一个偶数漂亮数组，那么A+B是一个漂亮数组
// 漂亮数组删除几个数后依然是漂亮数组
// 所以 N=1 ========[1]
// N=2 ========[1,2]
// N=3 =========[1,3,2]
// N=4 =========[1,3,2,4]
// N=5 =========[1,5,3,2,4]
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
}
python3 解法, 执行用时: 44 ms, 内存消耗: 15.1 MB, 提交时间: 2022-11-27 13:03:27
class Solution:
def beautifulArray(self, N: int) -> List[int]:
return sorted(range(1, N + 1), key=lambda x: bin(x)[:1:-1])
python3 解法, 执行用时: 40 ms, 内存消耗: 15.3 MB, 提交时间: 2022-11-27 13:03:09
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)
java 解法, 执行用时: 0 ms, 内存消耗: 41 MB, 提交时间: 2022-11-27 12:59:55
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;
}
}