HHKB2020 C - Neq Min (300)
コンテスト中の解法
全ての数字の登場回数を記録しておく
全ての数字を見たときに含まれてない最小値を持っておく
配列を逆順に見ていく
見ている数が最小値未満ならその数の登場回数を1減らす
登場回数が0になった場合、その数は以降に現れないのでそれを最小値とする
登場回数の記録、最初の最小値の計算、最小値の更新はそれぞれ$ O(N)
解説の解法
現在の最小値を記録しておく
配列をそれぞれ見ていく
今見ている値の登場回数を増やす
現在の最小値が登場してしまっている場合、登場しない値になるまで最小値を更新する
登場していない値が答え
最小値の更新は$ Nに依らず最大$ 2 \ times 10^5回
配列を見るのが$ O(N)