k番目に小さい要素
整数 n 個とある数 k が与えられたとき、リストの中で k 番目に小さい要素を求めてください。配列の要素がすべて異なることは保証されています。
入力
最初の行には、2 つの整数 n と k が与えられます (1 ≤ k ≤ n ≤ )。
次の行には、n 個の整数 () が空白区切りで与えられます。
出力
与えられたリストの中で、k 番目に小さい要素を出力してください。
例
入力 | 出力 |
|---|---|
6 3 | 4 |
7 2 | -3 |
解説
リストをソートすると [-2, 3, 4, 6, 8, 10] となり、ここで 3 番目に小さい要素は 4 です。
リストをソートすると [-4, -3, 0, 5, 7, 8, 10] となり、2 番目に小さい要素は -3 です。
ヒント 1
QuickSort（クイックソート）のようにランダムな基準値（ピボット）を使って配列を分割する方法を利用できます。
要素数が の配列を単純にソートするのは、通常の時間制限では厳しいことがあります。
ヒント 2
ランダムに選んだピボットを使って配列を仕分けしたら、必要な部分だけを残し不要な部分は捨ててください。
この操作を繰り返し、捨てた要素の数が先にある k 番目の要素に対応するところまで行えばいいのです。
ランダムな分割を行うと平均的には線形時間 が期待できます。なぜだと思いますか？
ヒント 3
ランダムにピボットを選んで配列を分割するたびに、平均的には配列の大きさが半分になります。つまり、サイズ n の配列から始めたとすると、1 回目の分割後に n/2 が捨てられ、2 回目は n/4 分が捨てられ… という形で、合計すると捨てている量はおよそ となります。
ただし、ピボットが常に最悪の位置を引き当ててしまうと、最悪計算量は になる可能性があります。
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB