JZX轻语：简
LeetCode 969 - 煎饼排序
发表于2024年05月31日
挺好玩的排序，通过分析可知，其类似于冒泡or选择排序，一种可行的从大到小、从后往前排好数组做法是：当处理第i大的元素时，先将其翻转到首位(若其现在处在第j个位置，则翻转前j个元素)，然后再翻转到第i位即可。这样可以保证不会破坏已经排好且放置在数组最后的元素。
由于在翻转的过程中，每个元素的位置会发生多次变动，我们不必完全模拟翻转的全过程，可以利用前面的翻转结果来计算当前处理元素的现位置。即如果当前元素在数组的原位置为i，则翻转前j个位置后，新位置为j - 1 - i if i < j else i(即，如果原位置在翻转的子数组范围内，则计算镜像位置，否则还是原位置)，我们可以通过循环遍历翻转结果来计算当前元素目前的位置！
class Solution:
def pancakeSort(self, arr: List[int]) -> List[int]:
# 首先将arr倒序排序, 并记录原来在arr的位置
arr = sorted(((num, i) for i, num in enumerate(arr)), key=lambda item: -item[0])
ans = []
# 从大到小处理
for i, (num, pos) in enumerate(arr):
# i为当前处理第i大(0开始)的数, num为数值, pos为在原来数组的位置
# 需要计算此时的位置
# 新位置 = 翻转子数组长度 - 1 - 旧位置 if 处在翻转子数组内 else 旧位置
cur_pos = pos
for move in ans:
if move - 1 >= cur_pos:
cur_pos = (move - 1) - cur_pos
if cur_pos == len(arr) - i - 1: # 该元素目前所处的新位置刚好在第i大的位置, 无需翻转
continue
# 先把它翻在前面
if cur_pos != 0: # 已经在最前面了
ans.append(cur_pos + 1)
# 然后再翻到目的位置上, 挺类似冒泡or选择排序的
ans.append(len(arr) - i)
return ans