darn what is this algorithm

by math_explorer, Jan 30, 2014, 4:07 AM

maj = RANDOM_SENTINEL_VALUE # doesn't really matter
cnt = 0
for x in sequence:
    if x == maj: cnt += 1
    else:
        if cnt == 0: maj = x; cnt = 1
        else: cnt -= 1
 
# If more than half of the elements of sequence are the
# same, maj is that element. Another naive scan can
# verify this while preserving linear asymptotic time
# (and no extra memory as long as sequence is
# deterministically reconstructible on-the-fly)
 
cnt = 0
for x in sequence:
    if x == maj: cnt += 1
if cnt > len(sequence) // 2:
    # maj is the majority element
else:
    # no majority element

Comment

2 Comments

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
That's the Boyer-Moore Majority Algorithm. It runs O(n), obviously.
This post has been edited 2 times. Last edited by PythonNut, Jan 30, 2014, 5:02 AM

by PythonNut, Jan 30, 2014, 4:57 AM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
DARN IT HAS A NAME

gg

by math_explorer, Jan 30, 2014, 5:49 AM

♪ i just hope you understand / sometimes the clothes do not make the man ♫ // https://beta.vero.site/

avatar

math_explorer
Archives
+ September 2019
+ February 2018
+ December 2017
+ September 2017
+ July 2017
+ March 2017
+ January 2017
+ November 2016
+ October 2016
+ August 2016
+ February 2016
+ January 2016
+ September 2015
+ July 2015
+ June 2015
+ January 2015
+ July 2014
+ June 2014
inv
+ April 2014
+ December 2013
+ November 2013
+ September 2013
+ February 2013
+ April 2012
Shouts
Submit
  • how do you have so many posts

    by krithikrokcs, Jul 14, 2023, 6:20 PM

  • lol⠀⠀⠀⠀⠀

    by math_explorer, Jan 20, 2021, 8:43 AM

  • woah ancient blog

    by suvamkonar, Jan 20, 2021, 4:14 AM

  • https://artofproblemsolving.com/community/c47h361466

    by math_explorer, Jun 10, 2020, 1:20 AM

  • when did the first greed control game start?

    by piphi, May 30, 2020, 1:08 AM

  • ok..........

    by asdf334, Sep 10, 2019, 3:48 PM

  • There is one existing way to obtain contributorship documented on this blog. See if you can find it.

    by math_explorer, Sep 10, 2019, 2:03 PM

  • SO MANY VIEWS!!!
    PLEASE CONTRIB
    :)

    by asdf334, Sep 10, 2019, 1:58 PM

  • Hullo bye

    by AnArtist, Jan 15, 2019, 8:59 AM

  • Hullo bye

    by tastymath75025, Nov 22, 2018, 9:08 PM

  • Hullo bye

    by Kayak, Jul 22, 2018, 1:29 PM

  • It's sad; the blog is still active but not really ;-;

    by GeneralCobra19, Sep 21, 2017, 1:09 AM

  • dope css

    by zxcv1337, Mar 27, 2017, 4:44 AM

  • nice blog ^_^

    by chezbgone, Mar 28, 2016, 5:18 AM

  • shouts make blogs happier

    by briantix, Mar 18, 2016, 9:58 PM

91 shouts
Contributors
Tags
About Owner
  • Posts: 583
  • Joined: Dec 16, 2006
Blog Stats
  • Blog created: May 17, 2010
  • Total entries: 327
  • Total visits: 355984
  • Total comments: 368
Search Blog
a