煎饼排序——选择排序的运用
目录
题目
解题思路
读懂题目：
此题并不是要我们求出类似于示例所给的最优情况的方式得出答案。
他只要能够翻转成有序的操作序列即可。
故我们可以按照选择排序的思路，利用翻转能够将首尾交换，来进行两次翻转把最大值移动到最后的位置，第一次翻转到首位，第二次翻转到后面的位置即可。
具体例子：
例如:[3,2,4,1]—->[?,?,?,4]
我们可以先找到数字4的位置,将数字4前进行翻转变成[4,2,3,1],接下来我们在整体翻转[1,3,2,4],这样我们把数字4移动列表底.
然后,我们[1,3,2,4]—>[?,?,3,4],还是用刚才方法,首先找到数字3,翻转数字3前面的,再翻转已经排好数字(这里指数字4)前就可以了.
解题代码
class Solution {
public:
vector<int> pancakeSort(vector<int> &arr) {
int n = arr.size();
vector<int> ret;
while (n > 1) {
if (arr[n - 1] != n) {
int index = find_if(arr.begin(), arr.end(), [n](auto &num) {
if (num == n)
return true;
return false;
}) - arr.begin();
ret.push_back(index + 1);
ret.push_back(n);
reverse(arr.begin(), arr.begin() + index + 1);
reverse(arr.begin(), arr.begin() + n);
}
--n;
}
return ret;
}
};