用 Python 编写程序，查找对数组进行排序需要多少次交换

pythonserver side programmingprogramming更新于 2025/12/12 22:04:17

假设，我们有一个名为 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 := new list，其中包含 input_arr 中每个项目的元组 (item_postion, item)
- 根据 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))