Namaran

Code daily. Without assist.

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 を返すだけで、どちらの範囲外も扱えます。