finding the majority element in an array? - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

finding the majority element in an array?

finding the majority element in an array?# JobHunting - 待字闺中

p*i2012-02-17 08:02

1 楼

问一道题目，how to find the majority element in an array?
例如一个array里有 4,2,3,1,2,2,2 就要return 2(因为2出现的次数是4, 4超过了
array 长度的一半）。相反，如果array 里是4,2,3,1,2,2,3 就要return -1（因为没
有数超过array 长度的一半）。
如何在 O(n) 的time complexity 和O(1) 的space里完成？

c*e2012-02-17 08:02

2 楼

荷兰国旗问题听说过么，这个应该差不多

c*e2012-02-17 08:02

3 楼

http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html

p*i2012-02-17 08:02

4 楼

荷兰国旗问题没听说过，能说下吗？

【在 c*****e 的大作中提到】

: 荷兰国旗问题听说过么，这个应该差不多

p*i2012-02-17 08:02

5 楼

谢啦，很好的解释

【在 c*****e 的大作中提到】

: http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html

c*e2012-02-17 08:02

6 楼

就是1/3的问题

【在 p*****i 的大作中提到】

: 荷兰国旗问题没听说过，能说下吗？

p*i2012-02-17 08:02

7 楼

能具体点儿吗？先膜拜下

【在 c*****e 的大作中提到】

: 就是1/3的问题

c*e2012-02-17 08:02

8 楼

http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/

【在 p*****i 的大作中提到】

: 能具体点儿吗？先膜拜下

p*i2012-02-17 08:02

9 楼

hah,感谢啦

【在 c*****e 的大作中提到】

: http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/

i*e2012-02-17 08:02

10 楼

这题还有另一个解法，是用bit manipulation来做，当然没有那个之前发的链接优。如果是个数组里所有是32bit integer，循环三十二次，每一次只看第 k 个 significant bit，看 majority 的是 1 或者 0 bit。假设majority存在的话，那么 majority element 的第 k 个 bit 必定就是这个majority bit，以此类推。
这个问题也可以扩展成数组里有个数出现超过 1/k 次，找出那个 majority。方法类似。

p*i2012-02-17 08:02

11 楼

强大，学习了

如果是个数组里所有是32bit integer，循环三十二次，每一次只看第 k 个
significant bit，看 majority 的是 1 或者 0 bit。假设majority存在的话，那么
majority element 的第 k 个 bit 必定就是这个majority bit，以此类推。
似。

【在 i**********e 的大作中提到】

: 这题还有另一个解法，是用bit manipulation来做，当然没有那个之前发的链接优。如果是个数组里所有是32bit integer，循环三十二次，每一次只看第 k 个 significant bit，看 majority 的是 1 或者 0 bit。假设majority存在的话，那么 majority element 的第 k 个 bit 必定就是这个majority bit，以此类推。
: 这个问题也可以扩展成数组里有个数出现超过 1/k 次，找出那个 majority。方法类似。

j*b2012-02-17 08:02

12 楼

http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html
这个解法真的对么？
要是ABCDEFFF的情况用这个解法得出来的结果是F，但实际应该是不存在啊

s*t2012-02-17 08:02

13 楼

这个好像描述得不对呀，如果是
CACACACAB 最后就是B 1
但是B肯定不是majority呀？

【在 c*****e 的大作中提到】

: http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/

s*t2012-02-17 08:02

14 楼

握爪，我们想到一起去了。

【在 j****b 的大作中提到】

: http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html
: 这个解法真的对么？
: 要是ABCDEFFF的情况用这个解法得出来的结果是F，但实际应该是不存在啊

s*t2012-02-17 08:02

15 楼

想明白了，最后还必须再用最后的元素go through一遍整个array去确定是不是
majority. 这个最后元素不一定是整个array出现次数最多的元素。

r*n2012-02-17 08:02

16 楼

那样还是不行。拿他们自己的例子，取前面一部分，AAACCBB就不行。

【在 s******t 的大作中提到】

: 想明白了，最后还必须再用最后的元素go through一遍整个array去确定是不是
: majority. 这个最后元素不一定是整个array出现次数最多的元素。

p*u2012-02-17 08:02

17 楼

稍微修改一下
这样，用两个指针遍历整个数组的同时删除其中的元素，保证每次删除的时候都删掉两个不一样的元素，这样等没有元素可
删的时候，剩下的就是答案了

K*u2012-02-17 08:02

18 楼

现在看去思路很简单，当时居然是发了篇paper

s*t2012-02-17 08:02

19 楼

所以我说最后还要go through 整个array一遍去确认最后一个元素是不是majority,如
果不是就说明没有majority, 这个最后元素并不一定是在array里出现次数最多的元素。

【在 r*****n 的大作中提到】

: 那样还是不行。拿他们自己的例子，取前面一部分，AAACCBB就不行。

K*u2012-02-17 08:02

20 楼

和那个宴会名人题不是有异曲同工之处？

素。

【在 s******t 的大作中提到】

:
: 所以我说最后还要go through 整个array一遍去确认最后一个元素是不是majority,如
: 果不是就说明没有majority, 这个最后元素并不一定是在array里出现次数最多的元素。

p*i2012-02-17 08:02

21 楼

'majority' means (strictly) more than 50%
There is no majority element in AAACCBB.

【在 r*****n 的大作中提到】

: 那样还是不行。拿他们自己的例子，取前面一部分，AAACCBB就不行。

a*n2012-02-17 08:02

22 楼

这个算法的前提是必须有MAJORITY，如果没有，这个算法是不能用的。。。。所以它不
能解决第２种CASE。。。

w*o2012-02-17 08:02

23 楼

ihasleetcode,
你的bit manipulation方法对于有majority (超过1/2)的很好理解，也很简洁。
可是你说了可以扩展成超过 1/k次，这个比较难理解。比如说k=4, 有可能在数组中有
多个超过1/4次的数，这个怎么弄？
即使只有一个数超过了1/4次，用bit manipulation也没有方法找出来呀？！
谢谢！

如果是个数组里所有是32bit integer，循环三十二次，每一次只看第 k 个
significant bit，看 majority 的是 1 或者 0 bit。假设majority存在的话，那么
majority element 的第 k 个 bit 必定就是这个majority bit，以此类推。
似。

【在 i**********e 的大作中提到】

f*n2012-02-17 08:02

24 楼

可以。snapshot 已经说了，只需要完成之后check一下答案是不是majority。
你的意思是这个算法如果有majority肯定找到，但是如果没有majority可能找到没有，
也可能找到一个随机的错的元素。对不对？
但是这样的话，只需要check一下那个答案是不是majority。这个只需要O(n) time, O(
1) space，没有改变算法的complexity

【在 a*****n 的大作中提到】

: 这个算法的前提是必须有MAJORITY，如果没有，这个算法是不能用的。。。。所以它不
: 能解决第２种CASE。。。