969.煎饼排序

链接：969.煎饼排序
难度：Medium
标签：贪心、数组、双指针、排序
简介：给你一个整数数组 arr ，请使用 煎饼翻转 完成对数组的排序。

题解 1 - typescript

• 编辑时间：2021-03-15
• 执行用时：84ms
• 内存消耗：39.9MB
• 编程语言：typescript
• 解法介绍：每个值进行翻转到第一位，再翻转一次到最后一位进行比较。

function pancakeSort(arr: number[]): number[] {
  const len = arr.length;
  const indexes: number[] = [];
  const reverse = (last: number) => {
    for (let i = 0, j = last; i < j; i++, j--) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      [indexes[arr[i]], indexes[arr[j]]] = [indexes[arr[j]], indexes[arr[i]]];
    }
  };
  const ans: number[] = [];
  for (let i = 0; i < len; i++) indexes[arr[i]] = i;
  for (let i = len - 1; i >= 0; i--) {
    ans.push(indexes[i + 1] + 1);
    reverse(indexes[i + 1]);
    ans.push(i + 1);
    reverse(i);
  }
  return ans;
}

题解 2 - cpp

• 编辑时间：2022-02-19
• 执行用时：4ms
• 内存消耗：11MB
• 编程语言：cpp
• 解法介绍：每次翻转把最大值翻转到首位，再翻转到结尾。

class Solution {
   public:
    vector<int> pancakeSort(vector<int>& arr) {
        vector<int> ans;
        _pancakeSort(ans, arr, 0, arr.size() - 1);
        return ans;
    }
    void _pancakeSort(vector<int>& ans, vector<int>& arr, int start, int end) {
        if (end == 0) return;
        int vmax = start;
        for (int i = start; i <= end; i++) {
            if (arr[i] > arr[vmax]) vmax = i;
        }
        if (vmax != end) {
            reverse(arr, 0, vmax);
            ans.push_back(vmax + 1);
            reverse(arr, 0, end);
            ans.push_back(end + 1);
        }
        _pancakeSort(ans, arr, start, end - 1);
    }
    void reverse(vector<int>& arr, int start, int end) {
        for (int l = start, r = end; l < r; l++, r--) {
            swap(arr[l], arr[r]);
        }
    }
};