You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

969. 煎饼排序 - Pancake Sorting

. 2 min read

969. 煎饼排序 - Pancake Sorting

【双指针(BF)】 【双向链表(未完成)】

给定数组 A,我们可以对其进行煎饼翻转:我们选择一些正整数 k <= A.length,然后反转 A 的前 k 个元素的顺序。我们要执行零次或多次煎饼翻转(按顺序一次接一次地进行)以完成对数组 A 的排序。

返回能使 A 排序的煎饼翻转操作所对应的 k 值序列。任何将数组排序且翻转次数在 10 * A.length 范围内的有效答案都将被判断为正确。

Example:

示例 1:

输入:[3,2,4,1]
输出:[4,2,4,3]
解释:
我们执行 4 次煎饼翻转,k 值分别为 4,2,4,和 3。
初始状态 A = [3, 2, 4, 1]
第一次翻转后 (k=4): A = [1, 4, 2, 3]
第二次翻转后 (k=2): A = [4, 1, 2, 3]
第三次翻转后 (k=4): A = [3, 2, 1, 4]
第四次翻转后 (k=3): A = [1, 2, 3, 4],此时已完成排序。 

示例 2:

输入:[1,2,3]
输出:[]
解释:
输入已经排序,因此不需要翻转任何内容。
请注意,其他可能的答案,如[3,3],也将被接受。

提示:

  1. 1 <= A.length <= 100
  2. A[i][1, 2, ..., A.length] 的排列

Solutions

Solution 【双指针(BF)】 ( 11ms)

class Solution {
  public List<Integer> pancakeSort(int[] A) {
    List<Integer> result = new LinkedList<>();
    int curIdx = A.length;
    while (curIdx > 0) {
      int maxId = 0;
      for (int i = 0; i < curIdx; i++) {
        if (A[i] == curIdx) {
          maxId = i;
          break;
        }
      }
      if (maxId > 0) {
        result.add(maxId + 1);
        reverse(A, maxId + 1);
      }
      result.add(curIdx);
      reverse(A, curIdx);
      curIdx--;
    }
    return result;
  }

  private void reverse(int[] A, int idx) {
    int i = 0, j = idx - 1;
    while (i < j) {
      A[i] = A[i] ^ A[j];
      A[j] = A[i] ^ A[j];
      A[i] = A[i] ^ A[j];
      i++;
      j--;
    }
  }
}

复杂度分析

寻找极值 O(n)

翻转O(n)

Solution 【双向链表(未完成)】 ( ms)

Notes

目前没有看到复杂度上优化的算法,当前最快为10ms

优化思路:

将数组存在双向链表中,使用双指针来找到最大数字的位置。

每次寻找复杂度为O(n)

双向链表进行翻转时,复杂度O(1)