Pythonで各要素を左側の最小値に置き換えるプログラム

問題の概要

数値のリスト nums が与えられたとき、各要素 nums[i] を「その要素より左側にある要素の中で最も小さい値」に置き換えることを考えます。ただし、先頭の要素 nums[0] の左側には要素が存在しないため、0 に置き換えます。

例えば、入力が [15, 7, 9, 16, 12, 25] の場合、出力は [0, 15, 7, 7, 7, 7] となります。2番目以降の要素が、それぞれ自分より左側の最小値で置き換えられているのが分かりますね。

解き方のアプローチ

この問題は、リストを一度だけ走査しながら「それまでに見た最小値」を変数に保持しておくことで、O(n) の計算量で効率的に解くことができます。具体的な手順は以下の通りです。

• リスト nums が空の場合は、空のリストを返します。
• 変数 j に nums[0] の値を保存し、nums[0] を 0 に置き換えます。
• インデックス 1 からリストの末尾まで順に以下の処理を繰り返します。
  • 現在の要素を一時変数 k に退避させます。
  • nums[i] を j(これまでの最小値)に置き換えます。
  • j を j と k のうち小さい方の値で更新します。
• すべての処理が完了したら nums を返します。

実装例(Python)

以下に、上記の手順を実装したPythonコードを示します。

class Solution:
    def solve(self, nums):
        if not nums:
            return []
        j = nums[0]
        nums[0] = 0
        for i in range(1, len(nums)):
            k = nums[i]
            nums[i] = j
            j = min(j, k)
        return nums

ob = Solution()
nums = [15, 7, 9, 16, 12, 25]
print(ob.solve(nums))

入力

[15, 7, 9, 16, 12, 25]

出力

[0, 15, 7, 7, 7, 7]

コードの解説

このアルゴリズムの重要なポイントは、一時変数 k を使って元の値を退避させてから置き換えている点です。もし退避せずに nums[i] を直接書き換えてしまうと、次のステップで比較すべき「元の値」が失われてしまい、正しい結果が得られません。

また、リスト全体を1回だけ走査するため、時間計算量は O(n)、入力リスト自体を書き換える方式なら追加のメモリ使用量も O(1) に抑えられます。非常にシンプルかつ効率的な解法と言えるでしょう。