667-Beautiful_Arrangement_II-优美的排列II

667、优美的排列II

tag: python3 、 数组

---

题目描述

  给定两个整数 n 和 k，你需要实现一个数组，这个数组包含从 1 到 n 的 n 个不同整数，同时满足以下条件：

1. 如果这个数组是 [a1, a2, a3, ... , an] ，那么数组 [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] 中应该有且仅有 k 个不同整数；.

2. 如果存在多种答案，你只需实现并返回其中任意一种.

示例1

  输入: n = 3, k = 1
  输出: [1, 2, 3]
  解释: [1, 2, 3] 包含 3 个范围在 1-3 的不同整数， 并且 [1, 1] 中有且仅有 1 个不同整数 : 1

示例2

  输入: n = 3, k = 2
  输出: [1, 3, 2]
  解释: [1, 3, 2] 包含 3 个范围在 1-3 的不同整数， 并且 [2, 1] 中有且仅有 2 个不同整数: 1 和 2

提示

• n 和 k 满足条件 1 <= k < n <= 10^4.

---

题目链接

667.优美的排列II

---

题解

• 寻找符合要求的数组

  使用和 优美的排列 中类似的方法取寻找第一个满足条件的数组，但是超时了(后来没有继续优化不知道能不能实现不超时)

具体代码见 Beautiful Arrangement II.py

• 构造符合要求的数组

  题目中要求只需要返回任意一个符合要求的数组，那么就可以让人想到，只要我们能够找到一种构造方法那么就能够快速得得到结果。这里有两种构造方法：

1. 首先将 [1, 2, ..., n] 按顺序排列，我们知道如果在某一个位置 i 将 [i, ..., n] 旋转那么原数组就会从只有一种差值 1，变为 [1, 2, ..., n, n-1, ..., i] 有两种差值，之后在 i 之后的某一个位置 j 将旋转后的数组 [j, ..., i] 旋转，就又会产生一个新的差值，而这个差值必定必上一次产生的差值小

class Solution:
    def constructArray(self, n: int, k: int):
        res = list(range(1, n+1))
        for i in range(1, k):
            res[i:] = res[:i-1:-1]
        return res

 最终结果，运行时间372ms，超过37.50%；占用内存14.7MB，超过33.33%。由于进行了大量的数组旋转操作，效率还不是特别高。

2. 得到 n, k 后，首先排列前 n-k-1 个元素 [1, 2, ..., n-k-1]，这是只有一种差值 1，随后使用双指针分别指向 n-k 及 n，这里我们就可以发现剩下的数最大的差值为 n-(n-k) = k。随后我们按照顺序将左右指针插入数组末尾，这时左指针第一次插入造成的差值依旧为 1，后面的插入造成的差值为 |n-k+i - (n-(i-1))| = k-2i-1 ，而右指针插入造成的差值为 n-i - (n-k+i) = k-2i，因此小于 k 的所有值最后都会被取到，就构造出了 k 中差值 [1, 2, ..., k] 的优美数组。

class Solution:
    def constructArray(self, n: int, k: int):
        if n == 1:
            return None
        elif k == 1:
            return list(range(1, n+1))
        else:
            res = list(range(1, n-k))
            i, j = max(n-k, 1), n
            while i<=j:
                if i == j:
                    res.append(i)
                else:
                    res.append(i)
                    res.append(j)
                i += 1
                j -= 1
        return res

 最终结果，运行时间60ms，超过72.83%；占用内存14.5MB，超过50.00%。