leetcode 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

题解

可以知道A[k] * 2是一个偶数, 当 i < k < j时,为了使 A[k] * 2 != A[i] + A[j],可以让左边全奇数,右边全偶数

示例代码(go)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func beautifulArray(N int) []int {
res := make([]int, 0)

if N == 1 {
return []int{1}
}
left := beautifulArray((N +1) / 2)
right := beautifulArray(N / 2)

for _, v := range left {
res = append(res, 2 * v - 1)
}
for _, v := range right {
res = append(res, 2 * v)
}
return res
}