2026-11-10
kth_smallest.c
int partition(int* a, int lo, int hi);
int kth_smallest(int* a, int n, int k) {
}
長さ n の配列 a を小さい順に並べ替えたとき、添字 k の位置に来る値を返す kth_smallest を書いてください。a の中身は並べ替えてかまいません。partition(a, lo, hi) はすでにあり、a[lo] から a[hi] までを a[hi] の値を基準に並べ替えて、基準の値が入った位置 p を返します。このとき a[lo] から a[p - 1] までには基準より小さい値が、a[p + 1] から a[hi] までには基準以上の値が入ります。n は1以上で、k は0以上 n 未満です。
入力例 1
kth_smallest((int[]){7, 2, 9, 4, 5}, 5, 2)
出力例 1
5
入力例 2
kth_smallest((int[]){3, 1, 3, 2}, 4, 2)
出力例 2
3
入力例 3
kth_smallest((int[]){42}, 1, 0)
出力例 3
42
Reference
Reference
int partition(int* a, int lo, int hi);
int kth_smallest(int* a, int n, int k) {
int lo = 0;
int hi = n - 1;
for (;;) {
int p = partition(a, lo, hi);
if (p == k) {
return a[k];
}
if (k < p) {
hi = p - 1;
} else {
lo = p + 1;
}
}
}
partition が返した位置 p には、配列全体を並べ替えたときにもそこへ来る値が入っています。p より前には基準より小さい値しかなく、後ろには基準以上の値しかないので、並べ替えても基準の値は前後の境目から動かないからです。そこで p が k と等しければ a[k] が答えです。k が p より小さければ答えは a[lo..p-1] の中に、大きければ a[p+1..hi] の中にあるので、もう片方は二度と見ません。毎回片側だけに進むので、平均すると配列の長さに比例する手間で終わります。これは参考実装で、唯一の正解ではありません。再帰で書いてもかまいません。
lo と hi は配列全体での添字なので、範囲を狭めても k は書き換えずに済みます。入力例1では、基準の 5 を中心に分けると p は2で、そのまま k と一致して 5 を返します。入力例2のように同じ値があっても、基準と等しい値は後ろ側に入るだけで、p の値が並べ替えたときの位置であることは変わりません。範囲は1回ごとに基準の1個ぶん以上縮み、k は常に lo 以上 hi 以下に残るので、範囲が1個になれば必ず p == k で終わります。入力例3の n が1のときは、最初の partition がそうなります。