Leetcode 969 煎饼排序✨翻转间的数组排序艺术一、问题初识什么是煎饼排序二、算法核心思路从大到小逐个归位核心归位逻辑直观步骤演示以数组[3,4,2,1]为例三、编码实现C代码拆解核心思路梳理关键代码实现C代码关键细节讲解四、优化技巧⚡避免无效操作提升效率优化点1跳过已归位的元素优化点2避免翻转前1位优化效果五、算法性能分析时间复杂度空间复杂度适用场景六、总结算法与数据结构片头在算法的世界里总有一些趣味十足的经典问题煎饼排序便是其中之一它以独特的前n位翻转规则为约束让数组排序的过程变得像翻转煎饼一样充满巧思既考验对算法逻辑的理解也能锻炼编码实现的细节把控。今天我们就一起拆解这道经典算法题从解题思路到编码实现再到性能优化全方位解锁煎饼排序的奥秘一、问题初识什么是煎饼排序煎饼排序的核心规则十分简洁但却充满约束性我们只能对数组执行「翻转前n位」的操作通过若干次这样的翻转将一个无序数组调整为升序数组并输出任意一组可行的翻转方案即可答案不唯一。举个简单的例子现有数组[3,4,2,1]若第一次翻转前3位数组会变为[2,4,3,1]不是[4,2,3,1]原前三位3,4,2翻转后为2,4,3纠正原前三位3,4,2翻转后是2,4,3会议示例中为[3,4,2,1]翻转前三位得到[4,2,3,1]核心是前n位元素逆序排列若再翻转前4位整个数组逆序就会变成[1,3,2,4]。我们的目标就是通过这样的翻转操作让数组最终成为[1,2,3,4]这样的有序数组。这道题的魅力在于看似简单的翻转操作需要设计清晰的逻辑才能高效完成排序而其答案的不唯一性也给了我们充分的设计空间。二、算法核心思路从大到小逐个归位面对「仅能翻转前n位」的约束直接的升序排序思路会处处受限那换个角度思考——从大到小对元素进行归位这便是煎饼排序的核心解题思路一步一步让每个元素找到自己的“正确座位”。核心归位逻辑对于数组中的任意一个元素先从最大值开始再到次大值以此类推通过两次翻转完成归位第一次翻转找到当前待归位元素的位置翻转其位置之前的所有元素前index1位让该元素移动到数组第一位第二次翻转翻转前k位k为该元素的正确位置序号让该元素从第一位移动到正确的最终位置。直观步骤演示以数组[3,4,2,1]为例为了更清晰理解我们用图文结合的方式展示最大值4的归位过程原数组[3,4,2,1]最大值4的正确位置是第4位数组下标为3。第一步找到4的下标为1翻转前112位数组变为[4,3,2,1]4来到第一位第二步翻转前4位数组变为[1,2,3,4]4成功归位到最后一位。 次大值及后续元素的归位逻辑完全一致只需要在剩余未排序的子数组中重复上述两次翻转操作即可直到所有元素归位。三、编码实现C代码拆解理解了核心思路编码实现就水到渠成了。整个实现过程分为三大核心模块下标记录数组、翻转函数、主排序逻辑再配合细节优化让代码更高效、更健壮。核心思路梳理用index数组记录每个元素在原数组中的下标方便快速查找待归位元素的位置避免多次遍历数组编写通用的reverse翻转函数实现「翻转数组前n位」的功能并在翻转后更新index数组保证下标记录的准确性从最大值开始遍历到最小值对每个元素执行两次翻转若需要并记录每次的翻转步数最终输出翻转方案。关键代码实现C#include iostream #include vector #include algorithm using namespace std; // 翻转数组前n位并更新index数组 void reversePancake(vectorint arr, vectorint index, int n, vectorint res) { if (n 1) return; // 翻转前1位无意义直接返回 res.push_back(n); // 记录翻转的步数n int l 0, r n - 1; while (l r) { swap(arr[l], arr[r]); // 更新index数组交换后元素的下标同步更新 index[arr[l]] l; index[arr[r]] r; l; r--; } } // 煎饼排序主函数 vectorint pancakeSort(vectorint arr) { vectorint res; // 存储翻转方案 int n arr.size(); vectorint index(n 1); // 元素值为1~n下标从1开始更方便 // 初始化index数组记录每个元素的初始下标 for (int i 0; i n; i) { index[arr[i]] i; } // 从最大值到最小值逐个归位 for (int i n; i 1; i--) { // 优化如果元素已在正确位置无需处理 if (index[i] i - 1) continue; // 第一次翻转将当前元素翻到第一位 if (index[i] 1 ! 1) { // 避免无效翻转 reversePancake(arr, index, index[i] 1, res); } // 第二次翻转将当前元素翻到正确位置 if (i ! 1) { // 避免无效翻转 reversePancake(arr, index, i, res); } } return res; } // 测试主函数 int main() { vectorint arr {3,4,2,1}; vectorint res pancakeSort(arr); cout 翻转方案; for (int num : res) { cout num ; } cout endl; cout 排序后数组; for (int num : arr) { cout num ; } return 0; }代码关键细节讲解index数组的设计✨由于煎饼排序的数组元素通常为1~n的正整数若不是可做映射处理我们将index数组的大小设为n1元素值作为index数组的下标对应存储该元素在原数组中的位置。这样做的好处是O(1)时间查找任意元素的下标无需遍历数组大幅提升效率。reversePancake翻转函数该函数不仅完成数组前n位的翻转还会同步更新index数组——因为数组元素交换后其下标也发生了变化若不更新后续查找会出现错误。同时函数中直接记录翻转步数到结果数组res中简化主逻辑。主排序逻辑从最大值n遍历到最小值1对每个元素先判断是否已在正确位置index[i] i-1若是则直接跳过若不是执行两次翻转操作完成归位。四、优化技巧⚡避免无效操作提升效率煎饼排序的核心思路实现后还存在一些无效的翻转操作这些操作不仅不会改变数组状态还会增加结果数组的冗余因此我们需要做针对性优化让代码更高效。优化点1跳过已归位的元素如果当前待归位元素的下标已经等于其正确位置index[i] i-1说明该元素已经在最终位置无需进行任何翻转操作直接continue进入下一个元素的处理。优化点2避免翻转前1位翻转数组的前1位数组状态完全不变属于无意义操作。因此在第一次翻转翻到第一位和第二次翻转翻到正确位置时分别判断index[i]1 ! 1和i ! 1避免此类无效操作。优化效果经过上述优化后对于已经有序的数组如[1,2,3,4]算法会直接跳过所有操作结果数组为空实现了最优的时间复杂度。五、算法性能分析时间复杂度初始化index数组O(n)仅需一次遍历归位每个元素时最多执行两次翻转操作每次翻转的时间复杂度为O(k)k为翻转的前n位长度总共有n个元素因此翻转的总时间复杂度为O(n²)整体时间复杂度O(n²)这是煎饼排序的最优时间复杂度受限于翻转规则。空间复杂度额外使用了index数组和结果数组res空间复杂度为O(n)属于常数级额外空间空间效率较高。适用场景煎饼排序是一种基于翻转操作的排序算法适用于对排序操作有特殊约束的场景仅能翻转前n位虽然时间复杂度为O(n²)不如快速排序、归并排序等高效排序算法但在特定约束下是最优解同时其趣味化的解题思路也是算法学习中锻炼逻辑思维的经典案例。六、总结煎饼排序以其独特的翻转规则成为算法学习中一道经典的“思维题”其核心解题思路**「从大到小逐个归位」** 打破了常规的升序排序思维让我们学会在约束条件下换角度思考问题。从思路设计到编码实现再到细节优化我们完成了煎饼排序的全流程拆解用index数组实现元素下标的快速查找用通用翻转函数实现核心操作用三次优化避免无效操作最终实现了高效、健壮的煎饼排序代码。其实算法的魅力就在于此看似复杂的问题只要找到核心逻辑一步步拆解就能化繁为简。希望这篇文章能让你对煎饼排序有清晰的理解也能在后续的算法学习中养成多角度思考、重细节实现的习惯✨ 最后留一个小思考如果数组元素不是1~n的正整数该如何修改代码实现煎饼排序呢欢迎在评论区交流
Leetcode 969 煎饼排序✨：翻转间的数组排序艺术
发布时间：2026/7/28 13:13:06
Leetcode 969 煎饼排序✨翻转间的数组排序艺术一、问题初识什么是煎饼排序二、算法核心思路从大到小逐个归位核心归位逻辑直观步骤演示以数组[3,4,2,1]为例三、编码实现C代码拆解核心思路梳理关键代码实现C代码关键细节讲解四、优化技巧⚡避免无效操作提升效率优化点1跳过已归位的元素优化点2避免翻转前1位优化效果五、算法性能分析时间复杂度空间复杂度适用场景六、总结算法与数据结构片头在算法的世界里总有一些趣味十足的经典问题煎饼排序便是其中之一它以独特的前n位翻转规则为约束让数组排序的过程变得像翻转煎饼一样充满巧思既考验对算法逻辑的理解也能锻炼编码实现的细节把控。今天我们就一起拆解这道经典算法题从解题思路到编码实现再到性能优化全方位解锁煎饼排序的奥秘一、问题初识什么是煎饼排序煎饼排序的核心规则十分简洁但却充满约束性我们只能对数组执行「翻转前n位」的操作通过若干次这样的翻转将一个无序数组调整为升序数组并输出任意一组可行的翻转方案即可答案不唯一。举个简单的例子现有数组[3,4,2,1]若第一次翻转前3位数组会变为[2,4,3,1]不是[4,2,3,1]原前三位3,4,2翻转后为2,4,3纠正原前三位3,4,2翻转后是2,4,3会议示例中为[3,4,2,1]翻转前三位得到[4,2,3,1]核心是前n位元素逆序排列若再翻转前4位整个数组逆序就会变成[1,3,2,4]。我们的目标就是通过这样的翻转操作让数组最终成为[1,2,3,4]这样的有序数组。这道题的魅力在于看似简单的翻转操作需要设计清晰的逻辑才能高效完成排序而其答案的不唯一性也给了我们充分的设计空间。二、算法核心思路从大到小逐个归位面对「仅能翻转前n位」的约束直接的升序排序思路会处处受限那换个角度思考——从大到小对元素进行归位这便是煎饼排序的核心解题思路一步一步让每个元素找到自己的“正确座位”。核心归位逻辑对于数组中的任意一个元素先从最大值开始再到次大值以此类推通过两次翻转完成归位第一次翻转找到当前待归位元素的位置翻转其位置之前的所有元素前index1位让该元素移动到数组第一位第二次翻转翻转前k位k为该元素的正确位置序号让该元素从第一位移动到正确的最终位置。直观步骤演示以数组[3,4,2,1]为例为了更清晰理解我们用图文结合的方式展示最大值4的归位过程原数组[3,4,2,1]最大值4的正确位置是第4位数组下标为3。第一步找到4的下标为1翻转前112位数组变为[4,3,2,1]4来到第一位第二步翻转前4位数组变为[1,2,3,4]4成功归位到最后一位。 次大值及后续元素的归位逻辑完全一致只需要在剩余未排序的子数组中重复上述两次翻转操作即可直到所有元素归位。三、编码实现C代码拆解理解了核心思路编码实现就水到渠成了。整个实现过程分为三大核心模块下标记录数组、翻转函数、主排序逻辑再配合细节优化让代码更高效、更健壮。核心思路梳理用index数组记录每个元素在原数组中的下标方便快速查找待归位元素的位置避免多次遍历数组编写通用的reverse翻转函数实现「翻转数组前n位」的功能并在翻转后更新index数组保证下标记录的准确性从最大值开始遍历到最小值对每个元素执行两次翻转若需要并记录每次的翻转步数最终输出翻转方案。关键代码实现C#include iostream #include vector #include algorithm using namespace std; // 翻转数组前n位并更新index数组 void reversePancake(vectorint arr, vectorint index, int n, vectorint res) { if (n 1) return; // 翻转前1位无意义直接返回 res.push_back(n); // 记录翻转的步数n int l 0, r n - 1; while (l r) { swap(arr[l], arr[r]); // 更新index数组交换后元素的下标同步更新 index[arr[l]] l; index[arr[r]] r; l; r--; } } // 煎饼排序主函数 vectorint pancakeSort(vectorint arr) { vectorint res; // 存储翻转方案 int n arr.size(); vectorint index(n 1); // 元素值为1~n下标从1开始更方便 // 初始化index数组记录每个元素的初始下标 for (int i 0; i n; i) { index[arr[i]] i; } // 从最大值到最小值逐个归位 for (int i n; i 1; i--) { // 优化如果元素已在正确位置无需处理 if (index[i] i - 1) continue; // 第一次翻转将当前元素翻到第一位 if (index[i] 1 ! 1) { // 避免无效翻转 reversePancake(arr, index, index[i] 1, res); } // 第二次翻转将当前元素翻到正确位置 if (i ! 1) { // 避免无效翻转 reversePancake(arr, index, i, res); } } return res; } // 测试主函数 int main() { vectorint arr {3,4,2,1}; vectorint res pancakeSort(arr); cout 翻转方案; for (int num : res) { cout num ; } cout endl; cout 排序后数组; for (int num : arr) { cout num ; } return 0; }代码关键细节讲解index数组的设计✨由于煎饼排序的数组元素通常为1~n的正整数若不是可做映射处理我们将index数组的大小设为n1元素值作为index数组的下标对应存储该元素在原数组中的位置。这样做的好处是O(1)时间查找任意元素的下标无需遍历数组大幅提升效率。reversePancake翻转函数该函数不仅完成数组前n位的翻转还会同步更新index数组——因为数组元素交换后其下标也发生了变化若不更新后续查找会出现错误。同时函数中直接记录翻转步数到结果数组res中简化主逻辑。主排序逻辑从最大值n遍历到最小值1对每个元素先判断是否已在正确位置index[i] i-1若是则直接跳过若不是执行两次翻转操作完成归位。四、优化技巧⚡避免无效操作提升效率煎饼排序的核心思路实现后还存在一些无效的翻转操作这些操作不仅不会改变数组状态还会增加结果数组的冗余因此我们需要做针对性优化让代码更高效。优化点1跳过已归位的元素如果当前待归位元素的下标已经等于其正确位置index[i] i-1说明该元素已经在最终位置无需进行任何翻转操作直接continue进入下一个元素的处理。优化点2避免翻转前1位翻转数组的前1位数组状态完全不变属于无意义操作。因此在第一次翻转翻到第一位和第二次翻转翻到正确位置时分别判断index[i]1 ! 1和i ! 1避免此类无效操作。优化效果经过上述优化后对于已经有序的数组如[1,2,3,4]算法会直接跳过所有操作结果数组为空实现了最优的时间复杂度。五、算法性能分析时间复杂度初始化index数组O(n)仅需一次遍历归位每个元素时最多执行两次翻转操作每次翻转的时间复杂度为O(k)k为翻转的前n位长度总共有n个元素因此翻转的总时间复杂度为O(n²)整体时间复杂度O(n²)这是煎饼排序的最优时间复杂度受限于翻转规则。空间复杂度额外使用了index数组和结果数组res空间复杂度为O(n)属于常数级额外空间空间效率较高。适用场景煎饼排序是一种基于翻转操作的排序算法适用于对排序操作有特殊约束的场景仅能翻转前n位虽然时间复杂度为O(n²)不如快速排序、归并排序等高效排序算法但在特定约束下是最优解同时其趣味化的解题思路也是算法学习中锻炼逻辑思维的经典案例。六、总结煎饼排序以其独特的翻转规则成为算法学习中一道经典的“思维题”其核心解题思路**「从大到小逐个归位」** 打破了常规的升序排序思维让我们学会在约束条件下换角度思考问题。从思路设计到编码实现再到细节优化我们完成了煎饼排序的全流程拆解用index数组实现元素下标的快速查找用通用翻转函数实现核心操作用三次优化避免无效操作最终实现了高效、健壮的煎饼排序代码。其实算法的魅力就在于此看似复杂的问题只要找到核心逻辑一步步拆解就能化繁为简。希望这篇文章能让你对煎饼排序有清晰的理解也能在后续的算法学习中养成多角度思考、重细节实现的习惯✨ 最后留一个小思考如果数组元素不是1~n的正整数该如何修改代码实现煎饼排序呢欢迎在评论区交流
