969_煎饼排序

难度：中等

题目

给你一个整数数组 arr ，请使用 煎饼翻转 完成对数组的排序。

一次煎饼翻转的执行过程如下：

  • 选择一个整数 k ，1 <= k <= arr.length
  • 反转子数组 arr[0…k-1]（下标从 0 开始）

例如，arr = [3,2,1,4] ，选择 k = 3 进行一次煎饼翻转，反转子数组 [3,2,1] ，得到 arr = [1,2,3,4] 。

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

示例

示例一：

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

示例二：

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

提示

  • 1 <= arr.length <= 100
  • 1 <= arr[i] <= arr.length
  • arr 中的所有整数互不相同（即，arr 是从 1 到 arr.length 整数的一个排列）

解题

因为煎饼排序的规则是选择一个整数 k，然后反转数组 arr[0]～arr[k-1]，可以看到每次排序都影响前 k 个元素，所以考虑每轮循环将最大元素放到数组最后面，因此循环从数组最长开始 for (int n=arr.length; n>1;n--)。

每次循环先找当前的最大值下标，如果下标是数组最后一个，就跳过，此轮不用排序。

1
2
3
4
5
6
7
8
9
int index = 0;
for (int i=1; i<n;i++){
  if (arr[i]>arr[index]){
    index = i;
  }
}
if (index == n-1){
  continue;
}

然后先翻转 0-index 的元素，使最大元素翻转到数组首

然后在翻转当前数组的元素，使最大元素翻转到数组尾

分别记录操作

1
2
3
4
5
6
// 反转 0-index，index 换到首位
reverse(arr,index);
// 然后反转整个数组，index 换到末尾
reverse(arr,n-1);
ans.add(index+1);
ans.add(n);

翻转前 index 个元素

1
2
3
4
5
6
7
public void reverse(int[] arr, int index){
  for (int i=0, j=index; i<j; i++,j--){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public List<Integer> pancakeSort(int[] arr) {
  List<Integer> ans = new ArrayList<>();
  for (int n=arr.length; n>1;n--){
    int index = 0;
    for (int i=1; i<n;i++){
      if (arr[i]>arr[index]){
        index = i;
      }
    }
    if (index == n-1){
      continue;
    }
    // 反转 0-index，index 换到首位
    reverse(arr,index);
    // 然后反转整个数组，index 换到末尾
    reverse(arr,n-1);
    ans.add(index+1);
    ans.add(n);
  }
  return ans;
}

public void reverse(int[] arr, int index){
  for (int i=0, j=index; i<j; i++,j--){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}