969.煎饼排序

煎饼排序

给定数组 arr，执行一系列煎饼翻转（反转子数组前 k 个元素），使其变为升序。返回任意有效的翻转序列。

示例 1:

输入：arr = [3,2,4,1]
输出：[4,2,4,3]

提示:

• 1 <= arr.length <= 100
• arr 是 1 到 arr.length 的排列

解析

从大到小将每个元素翻转到正确位置：先翻转到开头，再翻转到目标位置。

var pancakeSort = function (arr) {
  const result = [];
  const n = arr.length;

  for (let target = n; target > 1; target--) {
    const idx = arr.indexOf(target);
    if (idx !== target - 1) {
      if (idx > 0) {
        result.push(idx + 1);
        arr.splice(0, idx + 1, ...arr.slice(0, idx + 1).reverse());
      }
      result.push(target);
      arr.splice(0, target, ...arr.slice(0, target).reverse());
    }
  }

  return result;
};

时间复杂度 O(N^2)，空间复杂度 O(N)。