Skip to content

Instantly share code, notes, and snippets.

@vu3rdd
Last active August 29, 2015 14:13
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save vu3rdd/8a6e8d895d4fc6ed7195 to your computer and use it in GitHub Desktop.
Save vu3rdd/8a6e8d895d4fc6ed7195 to your computer and use it in GitHub Desktop.
Majority element in an array
module Majority where
zeroCrossing :: Eq a => [a] -> [(a, Int)]
zeroCrossing [] = []
zeroCrossing (x:xs) =
scanl f i xs
where f (u, count) v | u /= v && count /= 0 = (u, count - 1)
| u /= v && count == 0 = (v, count + 1)
| otherwise = (u, count + 1)
i = (x, 1)
findMajority :: Eq a => [a] -> Maybe a
findMajority [] = Nothing
findMajority (x:xs) = let (c, count) = foldl f i xs
in
if count == 0 then Nothing
else Just c
where f (u, count) v | u /= v && count /= 0 = (u, count - 1)
| u /= v && count == 0 = (v, count + 1)
| otherwise = (u, count + 1)
i = (x, 1)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment