题目描述

题目链接：969. Pancake Sorting

Given an array of integers A, We need to sort the array performing a series of pancake flips.

In one pancake flip we do the following steps:

• Choose an integer k where 0 <= k < A.length.
• Reverse the sub-array A[0…k].
  For example, if A = [3,2,1,4] and we performed a pancake flip choosing k = 2, we reverse the sub-array [3,2,1], so A = [1,2,3,4] after the pancake flip at k = 2.

Return an array of the k-values of the pancake flips that should be performed in order to sort A. Any valid answer that sorts the array within 10 * A.length flips will be judged as correct.

例子

例子 1

Input: A = [3,2,4,1]
Output: [4,2,4,3]
Explanation:
We perform 4 pancake flips, with k values 4, 2, 4, and 3.
Starting state: A = [3, 2, 4, 1]
After 1st flip (k = 4): A = [1, 4, 2, 3]
After 2nd flip (k = 2): A = [4, 1, 2, 3]
After 3rd flip (k = 4): A = [3, 2, 1, 4]
After 4th flip (k = 3): A = [1, 2, 3, 4], which is sorted.
Notice that we return an array of the chosen k values of the pancake flips.

例子 2

Input: A = [1,2,3]
Output: []
Explanation: The input is already sorted, so there is no need to flip anything.
Note that other answers, such as [3, 3], would also be accepted.

Note

• 1 <= A.length <= 100
• 1 <= A[i] <= A.length
• All integers in A are unique (i.e. A is a permutation of the integers from 1 to A.length).

解题思路

这道题涉及到 pancakeSort()， 一次 flip 表示反转前 k 个元素。要重复这个操作直至数组排好序。通过这个方法，我们可以想到，每一次先找到当前没排好序的最后一个位置的元素，假设在 i 处，即： A[i] = target，先将那个元素 target 通过 flip(i + 1) 将翻到最前面，再进行 flip(target) 一次翻到正确位置即可。这样对每一个元素我们最多需要 2 次将其放在正确位置，因此总的次数最多为 2 * A.length 符合题目要求。此外针对每一个元素，首先寻找其在数组中的位置 O(n)，第一次 flip O(n)，第二次 flip O(n)，所以总的时间复杂度为： O(n^2)，代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include <vector>
#include <algorithm>

class Solution {
public:
    std::vector<int> pancakeSort(std::vector<int>& A) {
        int n = A.size();
        std::vector<int> results;
        for (int target = n; target > 0; target--) {

            int index;
            // find current target from list
            for (index = 0; index < target; index++) {
                if (A[index] == target) break;
            }

            if (index == target - 1) continue;

            // reverse [0, index] to get target to the first of list
            if (index != 0) {
                flip(A, index + 1);
                results.push_back(index + 1);
            }

            // reverse [0, target - 1] to put target to correct position
            if (index != target - 1){
                flip(A, target);
                results.push_back(target);
            }

        }

        return results;
    }

private:
    // reverse the first k elements in the list
    void flip(std::vector<int>& A, int k) {
        std::reverse(A.begin(), A.begin() + k);
    }
};

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)