4 people like it.
Like the snippet!
The Dominator of Array
The dominator of array A is the value that occurs in more than half of the elements of A. It is a zero-indexed based array consisting of N integers (A [] with N length). To find the index array of the dominator from a A [], we can use a helpful function from Seq module call 'Seq.groupBy' to mitigate the implementation of a solution.
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
|
module Dominator =
/// A dominator occurs in more than half of an array's length
let dominator (arr: int []) =
// Define an index seq
let seqIndex = Seq.init (arr.Length) id
// Create groups based on key (i.e., the elements of the original arr)
let seqGroups = Seq.groupBy(fun i -> arr.[i]) seqIndex
seqGroups
// Find all the groups that the keys' occurrence is more than half of the original arr
|> Seq.filter(fun x -> (snd x) |> Seq.length >= arr.Length/2)
// Convert the result as an index array of the dominator
|> Seq.map snd |> Seq.concat |> Array.ofSeq
// Testing cases
let testArray1 = [|7;4;8;2;4;-1;4;4;4;4;6;4|]
let testArray2 = [|0;2;2;4;0;2;0;0;2;2;2;8;2;2;2;0;0;0|]
let testArray3 = [|1;2;3;4|]
(*Although sometimes returning an Option type would be desirable*)
// [|1; 4; 6; 7; 8; 9; 11|]
dominator testArray1
// [|1; 2; 5; 8; 9; 10; 12; 13; 14|]
dominator testArray2
// [||]
dominator testArray3
|
val dominator : arr:int [] -> int []
Full name: Script.Dominator.dominator
A dominator occurs in more than half of an array's length
val arr : int []
Multiple items
val int : value:'T -> int (requires member op_Explicit)
Full name: Microsoft.FSharp.Core.Operators.int
--------------------
type int = int32
Full name: Microsoft.FSharp.Core.int
--------------------
type int<'Measure> = int
Full name: Microsoft.FSharp.Core.int<_>
val seqIndex : seq<int>
module Seq
from Microsoft.FSharp.Collections
val init : count:int -> initializer:(int -> 'T) -> seq<'T>
Full name: Microsoft.FSharp.Collections.Seq.init
property System.Array.Length: int
val id : x:'T -> 'T
Full name: Microsoft.FSharp.Core.Operators.id
val seqGroups : seq<int * seq<int>>
val groupBy : projection:('T -> 'Key) -> source:seq<'T> -> seq<'Key * seq<'T>> (requires equality)
Full name: Microsoft.FSharp.Collections.Seq.groupBy
val i : int
val filter : predicate:('T -> bool) -> source:seq<'T> -> seq<'T>
Full name: Microsoft.FSharp.Collections.Seq.filter
val x : int * seq<int>
val snd : tuple:('T1 * 'T2) -> 'T2
Full name: Microsoft.FSharp.Core.Operators.snd
val length : source:seq<'T> -> int
Full name: Microsoft.FSharp.Collections.Seq.length
val map : mapping:('T -> 'U) -> source:seq<'T> -> seq<'U>
Full name: Microsoft.FSharp.Collections.Seq.map
val concat : sources:seq<#seq<'T>> -> seq<'T>
Full name: Microsoft.FSharp.Collections.Seq.concat
module Array
from Microsoft.FSharp.Collections
val ofSeq : source:seq<'T> -> 'T []
Full name: Microsoft.FSharp.Collections.Array.ofSeq
val testArray1 : int []
Full name: Script.Dominator.testArray1
val testArray2 : int []
Full name: Script.Dominator.testArray2
val testArray3 : int []
Full name: Script.Dominator.testArray3
More information