难度: Medium
如果长度为 n 的数组 nums 满足下述条件，则认为该数组是一个 漂亮数组 ：
nums 是由范围 [1, n] 的整数组成的一个排列。0 <= i < j < n ，均不存在下标 k（i < k < j）使得 2 * nums[k] == nums[i] + nums[j] 。给你整数 n ，返回长度为 n 的任一 漂亮数组 。本题保证对于给定的 n 至少存在一个有效答案。
示例 1 ：
输入：n = 4 输出：[2,1,4,3]
示例 2 ：
输入：n = 5 输出：[3,1,2,5,4]
提示：
1 <= n <= 1000运行时间: 20 ms
内存: 16.1 MB
class Solution:
def beautifulArray(self, n: int) -> List[int]:
if n==1:
return [1]
if n&1==0:
tmp = self.beautifulArray(n//2)
return [2*tmp[i]-1 for i in range(n//2)] + [2*tmp[i] for i in range(n//2)]
if n&1 == 1:
odd = self.beautifulArray(int(n/2+0.5))
even = self.beautifulArray(int(n/2-0.5))
for i in range(len(odd)):
odd[i]=2*odd[i]-1
for i in range(len(even)):
even[i] = 2*even[i]
return odd+even
这个题解利用了递归和分治的思想来构建漂亮数组。漂亮数组的一个关键特性是，如果一个数组是漂亮的，那么它的任何线性变换形式也是漂亮的。例如，如果array是漂亮数组，那么对于任意整数a和b，数组a * array + b也是漂亮的。基于这个性质，可以通过递归地构造较小的漂亮数组来构建更大的漂亮数组。具体来说：1. 如果n为1，直接返回[1]。2. 对于偶数n，先递归调用构造长度为n/2的漂亮数组，然后通过对这个数组的元素进行线性变换生成整个数组，前半部分元素通过2*x-1变换，后半部分通过2*x变换。3. 对于奇数n，将其拆分为两部分进行递归构造，然后同样通过线性变换合并得到结果。
时间复杂度: O(n log n)
空间复杂度: O(n log n)
class Solution:
def beautifulArray(self, n: int) -> List[int]:
if n==1:
return [1] # 基础情况：n为1时，返回[1]
if n&1==0:
tmp = self.beautifulArray(n//2) # 递归构造长度为n/2的数组
return [2*tmp[i]-1 for i in range(n//2)] + [2*tmp[i] for i in range(n//2)] # 通过线性变换构造整个数组
if n&1 == 1:
odd = self.beautifulArray(int(n/2+0.5)) # 递归构造长度为n/2+1的数组
even = self.beautifulArray(int(n/2-0.5)) # 递归构造长度为n/2的数组
for i in range(len(odd)):
odd[i]=2*odd[i]-1 # 对奇数部分的元素进行2*x-1的变换
for i in range(len(even)):
even[i] = 2*even[i] # 对偶数部分的元素进行2*x的变换
return odd+even # 合并两部分得到最终结果
在设计漂亮数组的算法中，将n分为奇数和偶数两种情况处理是为了简化构造过程并利用递归的方式有效构建出漂亮数组。对于偶数n，可以直接将问题规模减半，然后通过对半分的结果应用线性变换（2*x-1和2*x）来构建整个数组，这样做的好处是可以保持数组的'漂亮'性质且易于操作。而对于奇数n，因为它无法直接平均分成两个相同的小部分，所以需要稍作调整，将其拆分成两个接近相等的部分（n/2+1和n/2），这样处理可以确保无论n的奇偶性，都能适应这种递归分治的模式，从而构造出满足条件的漂亮数组。
漂亮数组的定义中包含了一个重要的数学特性：如果一个数组是漂亮的，那么对其元素进行任何形式的线性变换后，得到的新数组也保持漂亮。这是因为漂亮数组的条件是对于任意的i, j, k，只要满足i < k < j，就不会有a[i] + a[j] = 2*a[k]。当对数组中的每个元素应用2*x-1或2*x这样的线性变换时，原本数组的相对顺序和差异保持不变，从而新数组同样满足漂亮数组的条件。这种线性变换实质上是在放大数组元素的值并进行位移，但不改变元素之间的相对差异和顺序，因此漂亮的性质得以保持。
对于n为奇数时，选择将n分为`n/2+1`和`n/2`两部分是因为n不能被2整除，因此需要将其拆分成两个尽量平均但不完全相等的部分，以便可以分别对这两部分继续应用递归构造漂亮数组的策略。这种分法允许算法适用于任何大小的数组，无论其奇偶性。此分法的核心效果在于保持了递归方法的一致性和可行性，因为每一步递归都能够处理任何大小的n。这种分割方式确保了算法的广泛适用性且对最终结果的漂亮属性没有负面影响。