Namaran

Code daily. Without assist.

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 がそうなります。