k番目に小さい要素
整数
n 個とある数 k が与えられたとき、リストの中で k 番目に小さい要素を求めてください。配列の要素がすべて異なることは保証されています。入力
最初の行には、2 つの整数
n と k が与えられます (1 ≤ k ≤ n ≤ )。次の行には、
n 個の整数 () が空白区切りで与えられます。出力
与えられたリストの中で、
k 番目に小さい要素を出力してください。例
入力 | 出力 |
6 3
10 -2 4 8 3 6 | 4 |
7 2
-4 5 8 -3 10 0 7 | -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 分が捨てられ… という形で、合計すると捨てている量はおよそ n + n/2 + n/4 + ... = 2n となります。ただし、ピボットが常に最悪の位置を引き当ててしまうと、最悪計算量は になる可能性があります。
Constraints
Time limit: 2.5 seconds
Memory limit: 512 MB
Output limit: 1 MB