LC 969. 煎饼排序

题目描述

这是 LeetCode 上的 969. 煎饼排序 ，难度为 中等。

给你一个整数数组 arr，请使用 煎饼翻转 完成对数组的排序。

一次煎饼翻转的执行过程如下：

• 选择一个整数 k ，$1 <= k <= arr.length$
• 反转子数组 arr[0...k-1]（下标从 $0$ 开始）

例如，arr = [3,2,1,4]，选择 k = 3 进行一次煎饼翻转，反转子数组 [3,2,1] ，得到 arr = [1,2,3,4] 。

以数组形式返回能使 arr 有序的煎饼翻转操作所对应的 k 值序列。任何将数组排序且翻转次数在 10 * arr.length 范围内的有效答案都将被判断为正确。

示例 1：

输入：[3,2,4,1]

输出：[4,2,4,3]

解释：
我们执行 4 次煎饼翻转，k 值分别为 4，2，4，和 3。
初始状态 arr = [3, 2, 4, 1]
第一次翻转后（k = 4）：arr = [1, 4, 2, 3]
第二次翻转后（k = 2）：arr = [4, 1, 2, 3]
第三次翻转后（k = 4）：arr = [3, 2, 1, 4]
第四次翻转后（k = 3）：arr = [1, 2, 3, 4]，此时已完成排序。 

示例 2：

输入：[1,2,3]

输出：[]

解释：
输入已经排序，因此不需要翻转任何内容。
请注意，其他可能的答案，如 [3，3] ，也将被判断为正确。

提示：

• $1 <= arr.length <= 100$
• $1 <= arr[i] <= arr.length$
• arr 中的所有整数互不相同（即，arr 是从 1 到 arr.length 整数的一个排列）

---

冒泡排序

由于每次我们都对「某段前缀」进行整体翻转，并且规定了翻转次数在一定范围内的方案均为合法翻转方案，同时 $arr$ 又是 $1$ 到 $n$ 的排列。

我们可以很自然想到「冒泡排序」：每次确定未排序部分最右端的元素（最大值）。

具体的，假设下标 $[k + 1, n - 1]$ 部分已有序，如果我们希望当前值 $t$ 出现在某个位置 $k$ 上，可以进行的操作为：

• 如果当前值 $t$ 已在 $k$ 上，无须进行操作；
• 如果当前值不在 $k$ 上，根据当前值是否在数组头部（下标为 $0$）进行分情况讨论：
  • 当前值在数组头部（下标为 $0$），直接将 $[0, k]$ 部分进行翻转（将 $k + 1$ 加入答案中），即可将当前值 $t$ 放到位置 $k$ 上；
  • 当前值不在数组头部（下标为 $0$），而是在 $idx$ 位置上，需要先将 $[0, idx]$ 部分进行翻转（将 $idx + 1$ 加入答案中），这样使得当前值 $t$ 出现数组头部（下标为 $0$），然后再将 $[0, k]$ 部分进行翻转（将 $k + 1$ 加入答案中），即可将当前值 $t$ 放到位置 $k$ 上。

而翻转某个前缀的操作可使用「双指针」实现，复杂度为 $O(n)$。

代码：

class Solution {
    public List<Integer> pancakeSort(int[] arr) {
        int n = arr.length;
        int[] idxs = new int[n + 10];
        for (int i = 0; i < n; i++) idxs[arr[i]] = i;
        List<Integer> ans = new ArrayList<>();
        for (int i = n; i >= 1; i--) {
            int idx = idxs[i];
            if (idx == i - 1) continue;
            if (idx != 0) {
                ans.add(idx + 1);
                reverse(arr, 0, idx, idxs);
            }
            ans.add(i);
            reverse(arr, 0, i - 1, idxs);
        }
        return ans;
    }
    void reverse(int[] arr, int i, int j, int[] idxs) {
        while (i < j) {
            idxs[arr[i]] = j; idxs[arr[j]] = i;
            int c = arr[i];
            arr[i++] = arr[j];
            arr[j--] = c;
        }
    }
}

• 时间复杂度：需要对 $n$ 个元素进行排序，每个元素最多触发两次翻转，每次翻转的复杂度为 $O(n)$。整体复杂度为 $O(n^2)$
• 空间复杂度：$O(n)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.969 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。