Pythonでリストを条件を満たす2つの部分に分割する際の前半部分の最小長を求めるプログラム

数値のリスト nums が与えられたとき、このリストを part1 と part2 の2つの部分に分割することを考えます。ただし、part1 のすべての要素は part2 のすべての要素以下である必要があります。このとき、part1 として可能な最短の長さ（長さ0は除く）を求めましょう。

例えば、入力が nums = [3, 1, 2, 5, 4] の場合、出力は 3 になります。これは、part1 = [3, 1, 2]、part2 = [5, 4] のように分割できるからです。

解決のための手順

この問題を解くには、以下の手順に従います。

• p := nums の最小値
• s := 0
• i を 0 から nums のサイズ - 1 まで繰り返す：
  • nums[i] が p と等しい場合：
    • s := i
    • ループを抜ける
• p := nums のインデックス 0 から s までの部分リストの最大値
• ans := s
• i を s + 1 から nums のサイズ - 1 まで繰り返す：
  • nums[i] < p の場合：
    • ans := i
• ans + 1 を返す

アルゴリズムのポイント

このアプローチの背景にある考え方は以下の通りです。

1. まずリスト全体の最小値を見つけ、その位置を特定します。最小値より前にある要素は、条件を満たすために必ず part1 に含める必要があります。
2. 次に、その位置までの範囲の最大値を求めます。この最大値よりも小さい要素が後続に存在する場合、その要素も part1 に含めるために境界を拡張する必要があります。
3. 最終的に、拡張された位置 + 1 が求める答えとなります。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

def solve(nums):
    p = min(nums)
    s = 0
    for i in range(len(nums)):
        if nums[i] == p:
            s = i
            break
    p = max(nums[: s + 1])
    ans = s
    for i in range(s + 1, len(nums)):
        if nums[i] < p:
            ans = i
    return ans + 1

nums = [3, 1, 2, 5, 4]
print(solve(nums))

入力

[3, 1, 2, 5, 4]

出力

3

このアルゴリズムの計算量は O(n) であり、リストを一度走査するだけで効率的に答えを求めることができます。