[Haskell-beginners] Re: Majority Element
daniel.is.fischer at web.de
Sun Feb 22 12:39:29 EST 2009
Am Sonntag, 22. Februar 2009 17:12 schrieb Keith Sheppard:
> > Message: 8
> > Date: Sun, 22 Feb 2009 01:15:30 +0000
> > From: "Matthew J. Williams" <matthewjwilliams1 at googlemail.com>
> > Subject: [Haskell-beginners] Majority Element
> > To: beginners at haskell.org
> > Message-ID: <49a0a726.278e420a.6b19.ffffe361 at mx.google.com>
> > Content-Type: text/plain; charset="us-ascii"; format=flowed
> > Dear listers
> > What is a majority element in an array?
> > Sincerely
> > Matthew J. Williams
The answer is implicit in Keith's code below, but let's state it also in plain
A majority element in a collection C of n things is a value that appears
strictly more than n/2 times in C.
In general, no majority element exists.
I had never met the term before Matthew's post. Does anybody know for what it
> I think this gets you what you want:
> majority nums = find (\x -> fromIntegral (length x) > (fromIntegral
> (length nums)) / 2) (group(sort(nums)))
You don't need the fromIntegral here, integer division does the right thing.
In case a majority element a exists, this returns Just [a,a...], so you might
add an "fmap head" to get the element itself.
> It returns a "Maybe" list containing all majority elements. Something
> that avoids the sort would be faster though.
Not the naive algorithm. However, if the type of elements doesn't belong to
Ord, we can't use sort :(
findMajority :: Eq a => [a] -> Maybe a
findMajority  = Nothing
findMajority xxs@(x:xs) = case sweep x 1 xs of
Nothing -> Nothing
Just candidate -> verify candidate 0 xxs
sweep a count 
| count == 0 = Nothing
| otherwise = Just a
sweep _ 0 (y:ys) = sweep y 1 ys
sweep a count (y:ys)
| a == y = sweep a (count+1) ys
| otherwise = sweep a (count-1) ys
verify c count (y:ys)
| c == y = verify c (count+1) ys
| otherwise = verify c (count-1) ys
verify c count 
| count > 0 = Just c
| otherwise = Nothing
More information about the Beginners