Pythonでソート後に正しい位置にある要素の数をカウントする方法

問題の概要

数値のリスト nums が与えられたとき、そのリストをソートした場合に元の位置から動かない要素（正しいインデックスに配置される要素）がいくつあるかを求めるプログラムをPythonで作成します。

例えば、入力が [2, 8, 4, 5, 11] の場合を考えてみましょう。このリストを昇順にソートすると [2, 4, 5, 8, 11] になります。比較すると、先頭の「2」と末尾の「11」はソート前後で同じ位置に留まっています。したがって、出力は 2 となります。

解決のアプローチ

この問題は、以下の手順でシンプルに解くことができます。

• リスト nums をソートした新しいリスト s を作成する
• カウンター count を 0 で初期化する
• 0 から nums のサイズまでループを回し、各インデックス i について s[i] と nums[i] を比較する
• 両者が一致していれば count を 1 増やす
• 最後に count を返す

それでは、実際の実装を見てみましょう。

実装例

class Solution:
   def solve(self, nums):
      s = sorted(nums)
      count = 0
      for i in range(len(nums)):
         if s[i] == nums[i]:
            count += 1
      return count
ob = Solution()
print(ob.solve([2, 8, 4, 5, 11]))

入力

[2, 8, 4, 5, 11]

出力

2

コードのポイント

この実装では、Pythonの組み込み関数 sorted() を使うことで元のリストを変更せずにソート済みのコピーを作成しています。これにより、元のリストとの比較が容易になります。計算量はソート部分が O(n log n)、比較部分が O(n) となるため、全体として O(n log n) の時間計算量で処理できます。また、zip() 関数を使えば sum(a == b for a, b in zip(nums, sorted(nums))) のように、より簡潔に同じ結果を得ることも可能です。