Python程序：查找对数组进行排序所需的交换次数

假设我们有一个名为nums的数组，我们需要找到使nums按任何顺序排序（升序或降序）所需的交换次数。

例如，如果输入是nums = [2, 5, 6, 3, 4]，则输出为2，因为最初nums是[2, 5, 6, 3, 4]。如果我们交换数字6和4，数组将变为[2,5,4,3,6]。然后，如果我们交换数字5和3，数组将变为[2,3,4,5,6]。因此，使数组按升序排序需要2次交换。

为了解决这个问题，我们将遵循以下步骤：

  • 定义一个函数`swap_count()`。它将接收`input_arr`作为输入。
    • pos := 创建一个新列表，包含输入数组中每个元素的元组 (元素位置, 元素)。
    • 根据`input_arr`中的元素对列表`pos`进行排序。
    • cnt := 0
    • 对于索引范围从0到`input_arr`的大小，执行：
      • 当True时，执行：
        • 如果`pos[index, 0]`与索引相同，则
          • 退出循环
        • 否则，
          • cnt := `swap_count` + 1
          • swap_index := `pos[index, 0]`
          • 交换`pos[index]`和`pos[swap_index]`的值。
    • 返回cnt
  • 在主函数/方法中，执行以下操作：
    • 返回`swap_count(input_arr)`和`swap_count(input_arr`的反序)`的最小值。

示例

让我们看看下面的实现，以便更好地理解：

def swap_count(input_arr):
   pos = sorted(list(enumerate(input_arr)), key=lambda x: x[1])
   cnt = 0

   for index in range(len(input_arr)):
      while True:
         if (pos[index][0] == index):
            break
         else:
            cnt += 1
            swap_index = pos[index][0]
            pos[index], pos[swap_index] = pos[swap_index], pos[index]

   return cnt

def solve(input_arr):
   return min(swap_count(input_arr), swap_count(input_arr[::-1]))

nums = [2, 5, 6, 3, 4]
print(solve(nums))

输入

[2, 5, 6, 3, 4]

输出

2

更新于：2021年10月7日

2K+ 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告