【解题报告】lintcode46主元素

题意

给出一组数字,其中某个数字占据了总数的1/2以上,就是主元素,找出它
o(n)复杂度

思路

使用贪心的思路,每次从数组中拿一个数字,就认为它是主元素,然后继续拿,如果不同,就把计数器减一,如果相同,就把计数器加一,当计数器到0,就把下一个数字又作为主元素,继续这个过程,到最后,拿在手上的就是主元素了。

例子

比如数组[1,2,2,2,1,1,1]
开始时,设置主元素为1,计数器为1
2 与 1 不同,计数器减一,为0
由于计数为0, 取下一个数为主元素,2
继续,下个仍然是2,计数器加一
下个数是1, 计数减一, 设1为主元素
剩下两个1
最后我们的主元素就是手上的1

代码

u3coding
A software developer

Leave a Comment

Your email address will not be published. Required fields are marked *

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.