跳转至

LeetCode: 932. 漂亮数组

1、题目描述

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

2、解题思路

  • 首先明确一下,如果一个数组X是漂亮数组
  • 那么2X(每个元素乘以2),也是漂亮数组
  • 那么2X-1(每个元素乘以2,减一),也是漂亮数组

满足下面条件的为漂亮数组:

每个 i < j,都不存在 k 满足 i < k < j 使得 A[k] * 2 = A[i] + A[j]
  • 由于奇数+偶数 = 奇数
  • 2* [奇数或偶数] = 偶数

因此,首先奇偶数分开,分成两部分,那么这两部分就满足这个条件,奇数部分为X,偶数部分为Y

然后对X进行拆分,将X的所有位向右移动一位,然后拆分奇偶

对Y进行拆分,将Y的所有位向右移动一位,然后拆分奇偶

  • 上面的操作可以用排序来做,如下:
class Solution:
    def beautifulArray(self, N: int) -> List[int]:
        return sorted(range(1, N + 1), key=lambda x: bin(x)[:1:-1])