JZX轻语：简
LeetCode 932 - 漂亮数组
发表于2024年05月26日
一个需要点巧思的分治构造题目，如何将一个漂亮数组分解为两个漂亮子数组A和B的构造，且对于任一选取于漂亮数组A的元素a和任一选取于漂亮数组B的元素b(即两端分别选择于不同的子数组)，均不存在a + b = 2 * c的情况。这里的c是a和b之间的任意元素。通过观察可以知道，对于一个等差数组，我们将奇数位置的元素放在子数组A，偶数位置的元素放在子数组B，则可以满足题目要求。因为对于任意的满足上述选取要求的a和b，c不会存在于该数组中。因此，我们可以通过递归的方式构造漂亮数组。
class Solution:
def beautifulArray(self, n: int) -> List[int]:
ans = [-1] * n
def build(l: int, r: int, arr: List[int]):
if l == r:
ans[l] = arr[0]
return
odd = arr[1::2]
even = arr[::2]
build(l, l + len(odd) - 1, odd)
build(l + len(odd), r, even)
build(0, n - 1, list(range(1, n + 1)))
return ans