Find the Smallest Common Number
昇順でソートされた3つの整数配列から、3つの配列すべてに共通する最小の数を見つける必要があります。
説明
昇順で並べ替えられた3つの整数配列が与えられ、3つの配列すべてに共通する最小の数を見つけるアルゴリズムを実装する。
以下の3つの配列を見てみましょう。解は6 で、すべての配列に共通する最小数です。
ヒント
- 昇順配列を活用する。
- 3つのポインターを使用する。
Solution
Runtime Complexity O(n)
Memory Complexity O(1)
解説
配列が昇順で並べ替えられるという事実を利用する方法を考えてみましょう。
3つの反復子(イテレータ)を同時に使用して、各配列を走査します。
各配列の最小値を持つ0番目のインデックスから配列を走査することから始められます。
3つのイテレータが指す配列インデックスの値が等しい場合、
すべての配列に存在する最小値(配列が昇順で並べ替えられているため)になるため、その値を返す。
それ以外の場合は、3つのポイントのうち最小の値を指すイテレータを確認し
次のインデックスを指すようにそのイテレータをインクリメントしていきます。
3つのイテレータのいずれかが配列の最後に到達したときに共通の番号が見つからなかった場合、Nullを返します。