题目描述
题目链接: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 from1
toA.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 |
|
- 时间复杂度:O(n^2)
- 空间复杂度:O(1)