ABC476 C - Third Largest Number

第3位の数

考え方

問題をよーく読むと、言っていることはゲームのランキングのようなものだとわかる。
データが $3$ つ以上ある場合に、その第 $3$ 位のところに表示する値を答えろ、ということである。

そう考えると、一度 $4$ 位以下に落ちたデータは、捨ててしまってもよいことがわかる。

実装方法はいくつかある。
解答例として、以下の $2$ パターンを作成してある。

$1$ つめは、priority_queueを用いるもの。
小さい方を取り出すようにしたものに、順番にデータを入れていく。
もし中身が $4$ つ以上になっていたら、最も小さいものを捨てる。
中身が $3$ つになっていたら先頭にあるものが第 $3$ 位なので、それを結果とする。

$2$ つめは、vectorを用いるもの。
データを追加して降順にソートし、$4$ 位であるものがあれば捨てる。
$3$ 番目が存在するなら、それが第 $3$ 位の値である。

どちらも保持する要素数は高々 $4$ 個なので、それを定数とみなせば計算量は $O(N)$ である。

入力を受け取る。

n: 5
a: {1, 2, 1, 2, 3}

左から順に値を追加しながら、大きい方から $3$ 個だけを残していく。

最初の $3$ 個は $1,2,1$ である。
大きい順に並べると $2,1,1$ なので、第 $3$ 位は $1$ である。

次に $2$ を追加すると、いったん $2,2,1,1$ の $4$ 個になる。
このうち第 $4$ 位の $1$ を削除すると、$2,2,1$ が残る。
したがって、第 $3$ 位は $1$ である。

最後に $3$ を追加すると、いったん $3,2,2,1$ の $4$ 個になる。
このうち第 $4$ 位の $1$ を削除すると、$3,2,2$ が残る。
したがって、第 $3$ 位は $2$ である。

したがって、出力は次のようになる。

1
1
2

特になし。

特になし。