p*****i
发帖数: 197 | 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*****e
发帖数: 737 | |
c*****e
发帖数: 737 | |
p*****i
发帖数: 197 | 4 荷兰国旗问题没听说过，能说下吗？
【在 c*****e 的大作中提到】
: 荷兰国旗问题听说过么，这个应该差不多
|
p*****i
发帖数: 197 | |
c*****e
发帖数: 737 | 6 就是1/3的问题
【在 p*****i 的大作中提到】
: 荷兰国旗问题没听说过，能说下吗？
|
p*****i
发帖数: 197 | 7 能具体点儿吗？ 先膜拜下
【在 c*****e 的大作中提到】
: 就是1/3的问题
|
c*****e
发帖数: 737 | |
p*****i
发帖数: 197 | |
i**********e
发帖数: 1145 | 10 这题还有另一个解法，是用bit manipulation来做，当然没有那个之前发的链接优。如果是个数组里所有是32bit integer，循环三十二次，每一次只看第 k 个 significant bit，看 majority 的是 1 或者 0 bit。假设majority存在的话，那么 majority element 的第 k 个 bit 必定就是这个majority bit，以此类推。
这个问题也可以扩展成数组里有个数出现超过 1/k 次，找出那个 majority。方法类似。 |
|
|
p*****i
发帖数: 197 | 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****b
发帖数: 108 | |
s******t
发帖数: 139 | 13
这个好像描述得不对呀， 如果是
CACACACAB 最后就是B 1
但是B肯定不是majority呀？
【在 c*****e 的大作中提到】
: http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/
|
s******t
发帖数: 139 | 14
握爪，我们想到一起去了。
【在 j****b 的大作中提到】
: http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html
: 这个解法真的对么？
: 要是ABCDEFFF的情况用这个解法得出来的结果是F，但实际应该是不存在啊
|
s******t
发帖数: 139 | 15 想明白了， 最后还必须再用最后的元素go through一遍整个array去确定是不是
majority. 这个最后元素不一定是整个array出现次数最多的元素。 |
r*****n
发帖数: 1285 | 16 那样还是不行。拿他们自己的例子，取前面一部分，AAACCBB就不行。
【在 s******t 的大作中提到】
: 想明白了， 最后还必须再用最后的元素go through一遍整个array去确定是不是
: majority. 这个最后元素不一定是整个array出现次数最多的元素。
|
p**********u
发帖数: 157 | 17 稍微修改一下
这样，用两个指针遍历整个数组的同时删除其中的元素，保证每次删除的时候都删掉两个不一样的元素，这样等没有元素可
删的时候，剩下的就是答案了 |
K*****u
发帖数: 241 | 18 现在看去思路很简单，当时居然是发了篇paper |
s******t
发帖数: 139 | 19
所以我说最后还要go through 整个array一遍去确认最后一个元素是不是majority,如
果不是就说明没有majority, 这个最后元素并不一定是在array里出现次数最多的元素。
【在 r*****n 的大作中提到】
: 那样还是不行。拿他们自己的例子，取前面一部分，AAACCBB就不行。
|
K*****u
发帖数: 241 | 20 和那个宴会名人题不是有异曲同工之处？
素。
【在 s******t 的大作中提到】
:
: 所以我说最后还要go through 整个array一遍去确认最后一个元素是不是majority,如
: 果不是就说明没有majority, 这个最后元素并不一定是在array里出现次数最多的元素。
|
|
|
p*i
发帖数: 411 | 21 'majority' means (strictly) more than 50%
There is no majority element in AAACCBB.
【在 r*****n 的大作中提到】
: 那样还是不行。拿他们自己的例子，取前面一部分，AAACCBB就不行。
|
a*****n
发帖数: 158 | 22 这个算法的前提是必须有MAJORITY，如果没有，这个算法是不能用的。。。。所以它不
能解决第２种CASE。。。 |
w****o
发帖数: 2260 | 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 的大作中提到】
: 这题还有另一个解法，是用bit manipulation来做，当然没有那个之前发的链接优。如果是个数组里所有是32bit integer，循环三十二次，每一次只看第 k 个 significant bit，看 majority 的是 1 或者 0 bit。假设majority存在的话，那么 majority element 的第 k 个 bit 必定就是这个majority bit，以此类推。
: 这个问题也可以扩展成数组里有个数出现超过 1/k 次，找出那个 majority。方法类似。
|
f*******n
发帖数: 12623 | 24 可以。snapshot 已经说了，只需要完成之后check一下答案是不是majority。
你的意思是这个算法如果有majority肯定找到，但是如果没有majority可能找到没有，
也可能找到一个随机的错的元素。对不对？
但是这样的话，只需要check一下那个答案是不是majority。这个只需要O(n) time, O(
1) space，没有改变算法的complexity
【在 a*****n 的大作中提到】
: 这个算法的前提是必须有MAJORITY，如果没有，这个算法是不能用的。。。。所以它不
: 能解决第２种CASE。。。
|
