Pythonで配列が指定範囲のすべての要素を含んでいるかどうかを判定する方法

nums という配列と、2つの整数 x、y があるとします。この2つの数値は範囲 [x, y] を定義しており、配列がこの範囲内のすべての要素を含んでいるかどうかを判定する必要があります。

たとえば、入力が nums = [5,8,9,6,3,2,4]、x = 2、y = 6 の場合、範囲内の要素 [2,3,4,5,6] がすべて配列に存在するため、出力は True になります。

解決のためのアプローチ

この問題は、配列の要素の符号を反転させて「訪問済み」のマークとして利用することで、追加のメモリを使わずに効率的に解くことができます。手順は以下の通りです。

• temp_range := y - x を計算します。
• 0 から配列 nums のサイズまで繰り返します。
  • |nums[i]| が x 以上かつ y 以下である場合:
    • z := |nums[i]| - x を計算します。
    • nums[z] > 0 であれば、nums[z] := -nums[z] として符号を反転し、その値が存在することを記録します。
• カウンタ cnt := 0 を初期化します。
• 0 から temp_range まで繰り返します。
  • i が配列のサイズ以上になった場合はループを抜けます。
  • nums[i] > 0 であれば、範囲内の値が欠けていることを意味するため False を返します。
  • それ以外の場合は cnt := cnt + 1 とします。
• cnt が (temp_range + 1) と等しくなければ False を返します。
• すべてのチェックを通過すれば True を返します。

このアルゴリズムの計算量は O(n)、追加のメモリ使用量は O(1) であり、非常に効率的です。ただし、配列の内容が書き換えられる点や、範囲内の値がインデックスの範囲に収まっている必要がある点には注意してください。

実装例

それでは、実際のコードを見て理解を深めましょう。

def solve(nums, x, y):
    temp_range = y - x
    # 範囲内の各値について、対応する位置の符号を反転してマークする
    for i in range(0, len(nums)):
        if abs(nums[i]) >= x and abs(nums[i]) <= y:
            z = abs(nums[i]) - x
            if nums[z] > 0:
                nums[z] = nums[z] * -1
    cnt = 0
    # 範囲内のすべての位置がマークされているか確認する
    for i in range(0, temp_range + 1):
        if i >= len(nums):
            break
        if nums[i] > 0:
            return False
        else:
            cnt += 1
    if cnt != temp_range + 1:
        return False
    return True

nums = [5,8,9,6,3,2,4]
x = 2
y = 6
print(solve(nums, x, y))

入力

[5,8,9,6,3,2,4], 2, 6

出力

True

このように、符号反転のテクニックを活用することで、セットや辞書などの補助データ構造を使わずに、範囲内の全要素の存在チェックを1回の走査で行うことができます。