Shohei Yoshida
Shohei Yoshida's Blog

Shohei Yoshida's Blog

LeetCode 1338. Reduce Array Size to The Half in F#

Shohei Yoshida's photo
Shohei Yoshida
·Aug 18, 2022·

1 min read

URL

leetcode.com/problems/reduce-array-size-to-..

Code

github.com/syohex/dotnet-study/blob/master/..

let minSetSize (arr: int list) : int =
    let rec minSetSize' counts i sum half nums =
        match counts with
        | [] -> nums
        | h :: t ->
            let sum' = sum + h

            if sum' >= half then
                i + 1
            else
                minSetSize' t (i + 1) sum' half nums


    let counts =
        arr
        |> List.fold
            (fun acc num ->
                match Map.tryFind num acc with
                | None -> Map.add num 1 acc
                | Some (v) -> Map.add num (v + 1) acc)
            Map.empty
        |> Map.values
        |> Seq.sortWith (fun a b -> compare b a)
        |> Seq.toList

    let half = arr.Length / 2
    let nums = counts.Length
    minSetSize' counts 0 0 half nums
 
Share this