题目

链接：

Level: Medium

Discription:

Given an array A, we can perform a pancake flip: We choose some positive integer k<= A.length, then reverse the order of the first k elements of A. We want to perform zero or more pancake flips (doing them one after another in succession) to sort the array A.

Return the k-values corresponding to a sequence of pancake flips that sort A. Any valid answer that sorts the array within 10 * A.length flips will be judged as correct.

Example 1:

Input: [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.

Note:

• 1 <= A.length <= 100
• A[i] is a permutation of [1, 2, ..., A.length]

代码

class Solution {public:    vector
    
      pancakeSort(vector
     
      & A) {        vector
      
        ret;        for(int i = 0;i < A.size()-1;i++)        {            auto maxpos = max_element(A.begin(),A.end()-i);            ret.push_back(maxpos-A.begin()+1);            ret.push_back(A.size()-i);               reverse(A.begin(),maxpos+1);            reverse(A.begin(),A.end()-i);        }        return ret;    }};
      
     
    

思考

• 算法时间复杂度为O(n^2),空间复杂度为O(1)，不算输出的空间。
• 这个题没想到低于n方复杂度算法，通过序列不断地交换以实现有序，好像不能低于n方了，因为快排也就是nlogn。这里注意要擅用C++的STL，reverse和max_element函数使用方便。这题还有个思路是用哈希数组记录每个值的位置，在交换时，同时交换该数组中的值，这样可以避免每次都遍历一遍数组寻找最大值。但是每次都顺带着反转位置信息数组的操作已经是O(n)复杂度了。所以对提高性能的帮助也有限，还占了O(n)的空间。