2026-11-06
Kth.hs
kth :: Int -> [Int] -> Maybe Int
リスト全体を並べ替えずに、小さい方から数えて k 番目(0始まり)の要素を返す kth を書いてください。同じ値が複数あれば別々の要素として数えます。k が負か、要素の個数以上なら Nothing を返します。
入力例 1
kth 2 [7, 1, 5, 3]
出力例 1
Just 5
入力例 2
kth 1 [4, 1, 4]
出力例 2
Just 4
入力例 3
kth 3 [2, 8, 6]
出力例 3
Nothing
Reference
Reference
import Data.List (partition)
kth :: Int -> [Int] -> Maybe Int
kth _ [] = Nothing
kth k (p : xs)
| k < n = kth k smaller
| k == n = Just p
| otherwise = kth (k - n - 1) larger
where
(smaller, larger) = partition (< p) xs
n = length smaller
先頭の p を基準に、残りを partition (< p) で p より小さい smaller とそれ以外の larger に分けます。小さい方から並べると smaller の n 個、p、larger の順になるので、k < n なら答えは smaller の中の k 番目、k == n なら p です。それより大きければ答えは larger の中にあり、前にある n + 1 個を引いた k - n - 1 番目を探します。進むのは片側だけなので、使わなかった側は並べ替えられません。p と等しい要素は larger に入るので、入力例2の2つの 4 は両方とも数えられます。これは参考実装で、唯一の正解ではありません。
範囲外の k のために長さを先に調べる必要はありません。k が要素の個数以上なら、右へ進むたびに k は残りの個数以上のまま減っていき、いつか空リストで呼ばれます。入力例3では p = 2 で n = 0、kth 2 [8, 6] に進み、次に p = 8 で n = 1 なので kth 0 [] になって Nothing です。k が負なら k < n がいつも成り立って左へ進み続け、やはり空リストに着きます。空リストの節で Nothing を返すだけで、どちらの範囲外も扱えます。