leetcode 969. 煎饼排序

题目

思路

可以借鉴冒泡排序的思想，每次将一个最大值翻转到最后

可以发现，将未排序数组中的最大值index位置翻转到最后的操作是

• 翻转[0, index]
• 翻转[0, i] i是未排序数组的末尾

代码

class Solution {
public:
    vector<int> pancakeSort(vector<int>& arr) {
        int len = arr.size();
        vector<int> ans;
        for(int i=len;i>1;--i){
            int index = max_element(arr.begin(), arr.begin()+i)-arr.begin();
            if(index == i-1)  continue;
            reverse(arr.begin(), arr.begin()+index+1);
            ans.push_back(index+1);
            reverse(arr.begin(), arr.begin()+i);
            ans.push_back(i);
        }
        return ans;
    }
};

赏

谢谢你请我吃糖果

支付宝

微信