发表于 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

• LC 题目链接