回答編集履歴
1
誤字修正
answer
CHANGED
|
@@ -1,9 +1,16 @@
|
|
|
1
1
|
ソートアルゴリズムは色々とありますが、
|
|
2
2
|
普通にソートをすれば、あとは k 番目に小さい値を取れば終了です。
|
|
3
3
|
|
|
4
|
+
例えばリストをクイックソートをして、k 番目に小さい値を取るというのは簡単そうです。
|
|
5
|
+
これも再帰を使っています。
|
|
6
|
+
* [pythonでquicksort](https://qiita.com/sbtseiji/items/6cfc38ccd48055166883)
|
|
7
|
+
|
|
4
8
|
ただ、恐らく題意としては、
|
|
5
9
|
二分ヒープを使って欲しいのかなと推測しています。
|
|
6
10
|
|
|
11
|
+
なぜなら全部をソートしなくても k 番目に小さい値を取れるので、
|
|
12
|
+
全てをソートするのに比べて、計算量が少し少なくて済むからです。
|
|
13
|
+
|
|
7
14
|
リストを heapify して、そのあと heappop を k 回せばいけますね。
|
|
8
15
|
heapify, heappop 共に再帰を使用しています。
|
|
9
16
|
|