### 题目描述 给你一个整数数组 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 范围内的有效答案都将被判断为正确。 ### 输入输出 #### 示例1 ``` 输入：[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]，此时已完成排序。 ``` #### 示例2 ``` 输入：[1,2,3] 输出：[] 解释： 输入已经排序，因此不需要翻转任何内容。 请注意，其他可能的答案，如 [3，3] ，也将被判断为正确 ``` **提示** - 1 <= arr.length <= 100 - 1 <= arr[i] <= arr.length - arr 中的所有整数互不相同（即，arr 是从 1 到 arr.length 整数的一个排列） ### 题目解答 #### 解题思路 1. 首先选择长度为arr的数组中最大值， 2. 反转从0———最大值所处位置的数组，这样最大值就放到了第一个位置， 3. 反转从0——arr数组长度，使得最大值就被放到了数组的末尾 4. 如法炮制确定前arr-1， arr-2...1位置的元素即可 反转序列长度：每次确定一个位置的数值需要反转2次，因此需要$$2\times(arr.length-1)$$得到结果，满足反转次数小于10倍 **算法复杂度** 时间复杂度： 确定前n个元素的最大值：需要遍历n, n-1, n-2...1个元素，总共需要遍历$$(1+n)n/2$$个元素 反转数组：需要反转$$2(n-1)$$次，需要反转的元素个数不超过$$(1+n)n$$个元素 因此整体的时间复杂度，$$O(n^2)$$ 空间复杂度： 只需开辟新的内存空间，记录每次的最大值即可，空间复杂度在，$$O(1)$$ ### 代码实现 ```java class Solution { public List<Integer> pancakeSort(int[] arr) { List<Integer> res = new ArrayList<>(); for(int i=arr.length-1;i>0;i--){ int max = Integer.MIN_VALUE; int max_i = 0; for(int j=0;j<=i;j++){ if(arr[j] > max){ max = arr[j]; max_i = j; } } res.add(max_i+1); reverse(arr, max_i+1); res.add(i+1); reverse(arr, i+1); } return res; } // 把前k个数字反转 public void reverse(int[] arr, int k){ for(int i=0;i<k/2;i++){ int tmp = arr[i]; arr[i] = arr[k-i-1]; arr[k-i-1] = tmp; } } } ``` 最后编辑：2024年04月23日 ©著作权归作者所有 赞 0 分享
最新回复