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+ 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告