Medium
题目描述
给你一个整数数组 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：
输入：arr = [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：
输入：arr = [1,2,3]
输出：[]
解释：输入已经排序，因此不需要翻转任何内容。
请注意，其他可能的答案，如 [3，3]，也将被判断为正确。
提示：
1 <= arr.length <= 1001 <= arr[i] <= arr.lengtharr中的所有整数互不相同（即，arr是从1到arr.length整数的一个排列）
解题思路
这道题的核心思路是贪心算法。我们需要逐个将最大的元素放到正确的位置。
基本思路：
- 从最大的元素开始处理，每次将当前未排序部分的最大元素移动到正确位置
- 对于每个最大元素，如果它不在正确位置，我们需要两步操作：
- 第一步：如果最大元素不在数组开头，先将它翻转到开头
- 第二步：将整个未排序部分翻转，使最大元素到达正确位置
具体步骤：
- 找到当前未排序部分（长度为 n）的最大元素位置
- 如果最大元素已在正确位置（索引 n-1），直接处理下一个
- 如果最大元素在开头（索引 0），直接翻转整个未排序部分
- 否则，先翻转 [0…maxIndex]，将最大元素移到开头，再翻转整个未排序部分
这个方法最多需要 2n 次翻转，满足题目要求的 10n 次限制。算法简单直观，易于理解和实现。
代码实现
class Solution {
public:
vector<int> pancakeSort(vector<int>& arr) {
vector<int> result;
int n = arr.size();
for (int size = n; size > 1; size--) {
// 找到当前未排序部分的最大元素位置
int maxIndex = 0;
for (int i = 1; i < size; i++) {
if (arr[i] > arr[maxIndex]) {
maxIndex = i;
}
}
// 如果最大元素已经在正确位置，跳过
if (maxIndex == size - 1) continue;
// 如果最大元素不在开头，先翻转到开头
if (maxIndex != 0) {
reverse(arr.begin(), arr.begin() + maxIndex + 1);
result.push_back(maxIndex + 1);
}
// 将最大元素翻转到正确位置
reverse(arr.begin(), arr.begin() + size);
result.push_back(size);
}
return result;
}
};
class Solution:
def pancakeSort(self, arr: List[int]) -> List[int]:
result = []
n = len(arr)
for size in range(n, 1, -1):
# 找到当前未排序部分的最大元素位置
max_index = arr[:size].index(max(arr[:size]))
# 如果最大元素已经在正确位置，跳过
if max_index == size - 1:
continue
# 如果最大元素不在开头，先翻转到开头
if max_index != 0:
arr[:max_index + 1] = arr[:max_index + 1][::-1]
result.append(max_index + 1)
# 将最大元素翻转到正确位置
arr[:size] = arr[:size][::-1]
result.append(size)
return result
public class Solution {
public IList<int> PancakeSort(int[] arr) {
List<int> result = new List<int>();
int n = arr.Length;
for (int size = n; size > 1; size--) {
// 找到当前未排序部分的最大元素位置
int maxIndex = 0;
for (int i = 1; i < size; i++) {
if (arr[i] > arr[maxIndex]) {
maxIndex = i;
}
}
// 如果最大元素已经在正确位置，跳过
if (maxIndex == size - 1) continue;
// 如果最大元素不在开头，先翻转到开头
if (maxIndex != 0) {
Array.Reverse(arr, 0, maxIndex + 1);
result.Add(maxIndex + 1);
}
// 将最大元素翻转到正确位置
Array.Reverse(arr, 0, size);
result.Add(size);
}
return result;
}
}
var pancakeSort = function(arr) {
const result = [];
const n = arr.length;
for (let size = n; size > 1; size--) {
// Find the index of the maximum element in the current unsorted portion
let maxIndex = 0;
for (let i = 1; i < size; i++) {
if (arr[i] > arr[maxIndex]) {
maxIndex = i;
}
}
// If the max element is already at the end, continue
if (maxIndex === size - 1) continue;
// If the max element is not at the beginning, flip to bring it to the front
if (maxIndex !== 0) {
result.push(maxIndex + 1);
reverse(arr, maxIndex);
}
// Flip to move the max element to its correct position
result.push(size);
reverse(arr, size - 1);
}
return result;
};
function reverse(arr, k) {
let left = 0;
let right = k;
while (left < right) {
[arr[left], arr[right]] = [arr[right], arr[left]];
left++;
right--;
}
}
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(n²) - 外层循环 n 次，每次需要找到最大元素位置需要 O(n) 时间 |
| 空间复杂度 | O(1) - 除了结果数组外，只使用常数额外空间（原地修改数组） |