Pythonで障害のあるリストから欠落した正しいセンサー値を検出するプログラム

問題の概要

2つのリスト nums1 と nums2 があるとします。これらはそれぞれセンサーが計測した値を表しています。どちらのリストにも重複した値は含まれていません。ところが、片方のリストには正確な計測値が記録されている一方で、もう片方のリストには障害によって不正なデータが混入しています。

障害のあるリストでは、末尾以外の値が1つ削除され、その代わりに誤った値がリストの末尾に追加されています。この記事では、削除されてしまった本来のセンサー値を特定するプログラムを紹介します。

具体例

たとえば、次の入力を考えてみましょう。

• nums1 = [5, 10, 15]
• nums2 = [10, 15, 8]

この場合の出力は 5 となります。nums1 が正しい値 [5, 10, 15] を保持しており、nums2 の側では「5」が削除され、代わりに誤った値「8」が末尾に挿入されているためです。

解き方：二分探索で不一致点を見つける

この問題は二分探索(バイナリサーチ)を使うことで効率よく解決できます。障害のあるリストには重要な特徴があります。それは、「ある位置を境にして、それより前は両リストの要素が一致し、その位置以降は1つずつずれる」というものです。この境界(最初に不一致となる位置)を二分探索で絞り込めば、削除された値を特定できます。

具体的な手順は以下の通りです。

1. low を 0、high を「nums1 のサイズ − 1」で初期化します。
2. low < high の間、次の処理を繰り返します。
   • mid := (low + high) // 2(小数点以下を切り捨て)
   • nums1[mid] と nums2[mid] が等しければ → low := mid + 1(不一致点は後半にある)
   • 等しくなければ → high := mid(不一致点は mid 以前にある)
3. ループ終了後、low は最初の不一致位置を指しています。nums1[low + 1] が nums2[low] と一致すれば nums1 が正しいリストなので nums1[low] を返し、そうでなければ nums2 が正しいので nums2[low] を返します。

最後の判定について補足すると、もし nums2 側で値が1つ抜けているなら、nums2 の要素は nums1 よりも1つ後ろの位置に対応します。つまり nums1[low + 1] == nums2[low] が成り立つとき、正しいのは nums1 ということになり、削除された値は nums1[low] です。逆の場合は nums2 が正しく、答えは nums2[low] となります。

Pythonでの実装例

def solve(nums1, nums2):
    low, high = 0, len(nums1) - 1

    while low < high:
        mid = (low + high) // 2
        if nums1[mid] == nums2[mid]:
            low = mid + 1
        else:
            high = mid

    return nums1[low] if nums1[low + 1] == nums2[low] else nums2[low]

nums1 = [5, 10, 15]
nums2 = [10, 15, 8]
print(solve(nums1, nums2))

入力

[5, 10, 15], [10, 15, 8]

出力

5

処理の流れを追ってみる

上記の例では、次のように探索が進みます。

1. 初期状態：low = 0、high = 2
2. 1回目：mid = 1。nums1[1] = 10 と nums2[1] = 15 は一致しないため、high = 1 に更新
3. 2回目：mid = 0。nums1[0] = 5 と nums2[0] = 10 も一致しないため、high = 0 に更新
4. low = high = 0 となりループ終了。最初の不一致位置はインデックス 0
5. nums1[1] = 10 と nums2[0] = 10 が一致するため、nums2 の方が1つずれている(= nums2 が障害側)。よって nums1[0] = 5 を返す

計算量

このアルゴリズムの時間計算量は O(log n) です。リスト全体を先頭から順に比較する線形探索(O(n))に比べ、データサイズが大きくなるほど圧倒的に高速に動作します。また、空間計算量は O(1) で、追加のメモリもほとんど必要ありません。センサーデータのような大量の時系列データを扱う場合に、この手法は特に有効です。