题目：漂亮数组

  • 对于某些固定的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

来源：力扣（LeetCode）第932题

链接：https://leetcode-cn.com/problems/beautiful-array

分析：

  • 根据题目的要求，所谓漂亮数组就是A[k] * 2 != A[i] + A[j]。
  • A[k] * 2一定是一个偶数，那么我们只需要让A[i] + A[j]是奇数就行了，如果我们把奇数放在左边，偶数放在右边，那么左右两边各取一个数相加一定是奇数。
  • 那么还有一个问题，若i是偶数，j也是偶数怎么办？
  • 如果我们要知道8个数的漂亮数组，首先8有4个奇数，4个偶数，我们需要知道4个数的漂亮数组，如果要知道4个数的漂亮数组又要分为2奇数，2偶数，直到为1个数时，漂亮数组为[1]。
  • 漂亮数组又有一个性质，如果我们把数组中每个元素都乘以a并且加上b(a,b为任意除0外的数)，那么它还是漂亮数组。
  • 同样的我们把奇偶两个漂亮数组相加，结果还是漂亮数组。
  • 既然如此，[1]是漂亮数组，那么我将1*2-1也是是漂亮数组，我将1*2也是漂亮数组，我把这两个数放在一起，也就是[1,2]也是漂亮数组。以此类推，4个数的漂亮数组就是[1,3,2,4],8个数就是[1,5,3,7,2,6,4,8]。如果数不足8个多于4个，我只需要把多余的拿掉就行了。
  • 通过这种方式，可以发现，比如奇数部分的数两数相加除以2要么是偶数，要么在中间根本找不到这个数。

代码：

  • 分治算法：

    class Solution:
def beautifulArray(self, N: int) -> List[int]:
    def divi(N):
        ans = {1: [1]}
        if N not in ans:
            odds = divi((N + 1) // 2)
            evens = divi(N // 2)
            ans[N] = [2 * odd - 1 for odd in odds] + [2 * even for even in evens]
        return ans[N]
    return divi(N)

  • 分治法的迭代版本：

    class Solution:
def beautifulArray(self, N: int) -> List[int]:
    ans = [1]
    while len(ans) < N:
        ans = [2 * odd - 1 for odd in ans] + [2 * even for even in ans]
    return [i for i in ans if i <= N]

复杂度分析：

  • 时间复杂度：O(nlogn)
  • 空间复杂度：O(n)