Pythonでシーケンスをソートするために必要なスワップの数を見つけるためのプログラム

個別の番号のリストがあるとします。リストを昇順で並べ替えるのに必要なスワップの最小数を見つける必要があります。

したがって、入力がnums =[3、1、7、5]の場合、出力は2になります。これは、3と1、次に5と7を入れ替えることができるためです。

これを解決するには、次の手順に従います。

• sort_seq：=リスト番号を並べ替える
• テーブル：=新しいマップ
• 各インデックスiおよびnumsの値nについて、実行します
  • table [n]：=i
• スワップ：=0
• 0からnumsのサイズの範囲のiの場合は、
  • n：=nums [i]
  • s_n：=sort_seq [i]
  • s_i：=table [s_n]
  • s_nがnと同じでない場合、
    • スワップ：=スワップ+1
    • nums [s_i]：=n
    • nums [i]：=s_n
    • table [n]：=s_i
    • table [s_n]：=i
• リターンスワップ

理解を深めるために、次の実装を見てみましょう。

サンプルコード

class Solution:
def solve(self, nums):
   sort_seq = sorted(nums)
   table = {}

   for i, n in enumerate(nums):
      table[n] = i
   swaps = 0
   for i in range(len(nums)):
      n = nums[i]
      s_n = sort_seq[i]
      s_i = table[s_n]

      if s_n != n:
         swaps += 1
         nums[s_i] = n
         nums[i] = s_n
         table[n] = s_i
         table[s_n] = i

      return swaps

ob = Solution()
nums = [3, 1, 7, 5]
print(ob.solve(nums))

入力

[3, 1, 7, 5]

出力

2