URL

Kth Largest Element in an Array - LeetCode

Code

https://github.com/syohex/dotnet-study/tree/master/fsharp/leetcode/challenge/202308/kth_largest_element_in_an_array/main.fsx

let findKthLargest (nums: int list) (k: int) : int =
    let rec findKthLargest' nums k =
        match nums with
        | [] -> failwith "never reach here"
        | h :: [] -> h
        | pivot :: _ ->
            let lefts, rights, mids =
                nums
                |> List.fold
                    (fun (lefts, rights, mids) n ->
                        if n > pivot then n :: lefts, rights, mids
                        elif n < pivot then lefts, n :: rights, mids
                        else lefts, rights, mids + 1)
                    ([], [], 0)

            let leftLength = List.length lefts
            let leftAndMid = leftLength + mids

            if k <= leftLength  then
                findKthLargest' lefts k
            elif leftAndMid < k then
                findKthLargest' rights (k - leftAndMid)
            else
                pivot

    findKthLargest' nums k