集合の積 (intersection)

3000 件と 5000 件を突き合わせて 1500 万回

2 つの配列の両方に入っている値を集めます。素直に書けば、片方から値を 1 つ取り、もう片方に入っているかを見に行く形です。

問題は、その「入っているか」を配列に聞いていることです。配列は端から順に見るので、1 回聞くのに相手の件数ぶんかかります。3000 件と 5000 件なら 1500 万回。しかも、すでに拾った値かどうかを結果の配列に聞き直していると、その上にもう一段乗ります。

片方だけを、聞ける形に変える

両方を変える必要はありません。片方を先に集合にしておき、もう片方を 1 周するだけで済みます。

# 別題材 — 出席者に入っているかを聞く
attendees = set(attendee_list)   # 作るのは 1 回だけ
for name in applicants:
    if name in attendees:
        ...

集合を作るのに 3000 回、回すのに 5000 回。合わせて 8000 回まで落ちました。1500 万回との差は、聞き方を変えただけで生まれています。ループの数が減ったわけではありません。回すのは 1 周のままで、その中で聞く相手を配列から集合に替えただけです。

厄介なのは、この差がコードの見た目に出ないことです。Python の x in b は、b がリストなら端から探し、集合なら一発で返します。書いてある 2 文字は同じなのに速さがまるで違うので、聞いている相手が何なのかを毎回意識してください。

どちらを集合にするかは選べます。件数が少ないほうを集合にすれば、抱えておく量が減ります。ただし、回すほうを取り違えないでください。集合にした側を回してしまうと、聞く相手が配列に戻り、元の遅さに逆戻りします。

同じ値が 2 回出てくる

a = [1, 2, 2, 3] と b = [2, 3, 4] を突き合わせると、a の 2 が 2 つとも引っかかります。結果に素直に足していくと [2, 2, 3] になり、テストは落ちます。

拾った値を入れる側も、重複を持てない入れ物にしておけば、これは何もせずに消えます。「もう拾ったか」を毎回確かめる条件を書き足す必要はありません。片方を集合にした時点で b 側の重複も消えているので、両側に重複があっても大丈夫です。

出てくる順は約束されていない

最後に並べ替えます。集合から値を取り出す順は、入れた順とも小さい順とも限りません。言語や実装によって違いますし、同じ言語でも中身が変われば変わります。

手元で偶然そろっていると気づけないので、返す前に必ず昇順にしてください。[-3, -1, 0, 2] と [2, 0, -1, -5] のように負の数が混ざる場合も同じです。並べ替えたときに、負の数が正しく前へ来ているかを確かめてください。

共通する値が 1 つも無いときは、空の配列を返します。何も見つからなかったことを null で表すと、呼ぶ側の場合分けが増えます。

1. 入力を集合にして先に重複を除く
2. 共通値を通常の配列へ追加し、昇順に並べて返す
3. 所属確認は集合を使う。計算量は集合生成・確認が期待 O(n + m)、共通値 r 個のソートが O(r log r)