大家好，我是 @负雪明烛。👈👈 点击关注，优质题解不间断。

题目大意

煎饼排序。这个排序方式很有意思，每次可以把前 k 个数字进行翻转，问翻转多少次之后可以达到有序状态。

就像一摞煎饼一样，每次能把铲子插入煎饼中的某个位置，然后把铲子之上的煎饼都翻转一下，问一系列位置能使结果是排序的。

image.png
图源：wikiwand

解题方法

模拟法

重要思路：我们把后面的数字先排好序，这样再翻转前面的时候就不会影响到后面。

所以，先把最大的数字放到最后，然后再把次大的位置放在倒数第二个位置……

如何把最大的数字放到最后呢？一个很简单的想法就是先把它翻转到第一个位置上去！

所以，思路很清晰了：

  1. 每次找到还没排序的数字之中最大的数字的位置，把这个位置之前的数字翻转，这一步使得最大数字去了最前面；
  2. 第二步，再次翻转，把最大位置翻到它应该在的位置上去。

969. 煎饼排序.001.png

这个题目一个比较好的地方是：给的数字是 $1~N$ 的全排列，所以我们每次要找哪个数字很容易确定，不需要 $O(N)$ 的遍历去判断最大的数字是谁。

这个题目不好的地方是：给的第一个例子不是按照常规的煎饼排序的思想列出来的，否则大家肯定很容易想出来解法。

另外需要提醒大家，代码的结果和题目的序列是不一样的，但是提交可以通过。
image.png

C++代码如下：

  1. class Solution {
  2. public:
  3.     vector<int> pancakeSort(vector<int>& A) {
  4.         vector<int> res;
  5.         const int N = A.size();
  6.         int pos, i;
  7.         for (pos = N; pos > 0; pos--) {
  8.             for (i = 0; A[i] != pos; i ++);
  9.             reverse(A.begin(), A.begin() + i + 1);
  10.             if (i != 0)
  11.                 res.push_back(i + 1);
  12.             reverse(A.begin(), A.begin() + pos);
  13.             res.push_back(pos);
  14.         }
  15.         return res;
  16.     }
  17. };

Python 代码：

  1. class Solution(object):
  2.     def pancakeSort(self, A):
  3.         """
  4.         :type A: List[int]
  5.         :rtype: List[int]
  6.         """
  7.         N = len(A)
  8.         res = []
  9.         for x in range(N, 0, -1):
  10.             i = A.index(x)
  11.             res.extend([i + 1, x])
  12.             A = A[:i:-1] + A[:i]
  13.         return res

Java 代码：

  1. class Solution {
  2.     public List<Integer> pancakeSort(int[] A) {
  3.         List<Integer> res = new ArrayList<>();
  4.         int N = A.length;
  5.         int pos, i;
  6.         for (pos = N; pos > 0; pos--) {
  7.             for (i = 0; A[i] != pos; i ++);
  8.             reverse(A,0,  i );
  9.             if (i != 0)
  10.                 res.add(i + 1);
  11.             reverse(A,0, pos - 1);
  12.             res.add(pos);
  13.         }
  14.         return res;
  15.     }
  16.     private void reverse(int[] A, int start, int end) {
  17.         while (start < end) {
  18.             int tmp = A[start];
  19.             A[start] = A[end];
  20.             A[end] = tmp;
  21.             start ++;
  22.             end --;
  23.         }
  24.     }
  25. }
  • 时间复杂度：$O(N ^ 2)$，其中 $N$ 是数组长度；
  • 空间复杂度：$O(1)$。

总结

  1. 这就是冒泡排序的思想，学会基础理论知识，才能以不变应万变啊！

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。