leetcode#169: majority element

int[] nums={1,7,5,5,5,5,7,7,7,7}
10个元素，5出现4次，7出现5次，1出现1次

这个test case，预期结果，majority element为什么不是return 7, 而是5？

请大家看看，为我解惑，谢谢。

TongHeart 发表于 2020-09-28 08:42:29
不是7很显然是因为你遍历完之后没机会把candidate改成7
而且你这个test case就不对呀 不存在大于n/2=五次的数字，5和7都只是出现了四次
楼主学编程多长时间了？

我知道不符合要求，但是应该报错啊。况且7是出现5次的，看清楚。

只是5次还不够，但是发现了中文版leetcode 的这个问题. 不信自己去试试看吧。

不是7很显然是因为你遍历完之后没机会把candidate改成7
而且你这个test case就不对呀 不存在大于n/2=五次的数字，5和7都只是出现了四次
楼主学编程多长时间了？

理解了，majority 的定义是多于一半，所以题目中的test case ，等于一半，是不符合要求的.

只是中文版的LeetCode 要报错，而不是出预期结果。有个现象很有意思，如果你用HashMap写代码，这个test case会return 7，而预期结果还是5，但是你提交也是通过的。

英文版的LeetCode 会报错， no majority element.

现在有个问题，那这个test case找出现最多的元素而不是出现多于一半的，是不能用voting algorithm达到时间O（n),空间O（1）。那还有什么办法可以达到目标吗？随机法理论上可以...

大家➕大米啊，好多都看不了，多谢。

应该是中文版的问题了。。

dacheng0413 发表于 2020-09-28 12:17:28
应该是中文版的问题了。。

是的，中文版有问题. 我怀疑它的标准答案就是从voting algorithm中得到的。要不然HashMap是返回7的. 已经报告了问题，等他们回复中....

AmberCBDP 发表于 2020-09-28 08:57:50
我知道不符合要求，但是应该报错啊。况且7是出现5次的，看清楚。

只是5次还不够，但是发现了中文版leetcode 的这个问题. 不信自己去试试看吧。

不好意思，昨晚太晚了眼花了，他这个确实是有问题

AmberCBDP 发表于 2020-9-28 23:52
理解了，majority 的定义是多于一半，所以题目中的test case ，等于一半，是不符合要求的.

只是中文版的Le ...

你有很多个元素一边多 比如sqrt(n)种元素 都是sqrt(n)那么多 咋可能用O(1)的空间记录的下来呢

anhpp 发表于 2020-09-28 18:53:31
你有很多个元素一边多 比如sqrt(n)种元素 都是sqrt(n)那么多 咋可能用O(1)的空间记录的下来呢

我是以这个为例子，如果一个数组中有元素出现ceiling (size/2)次，>=ceiling(size/2),因为有等号，所以不能用投票法，可以用官方题解中的随机法，达到时间O(n),空间O(1)

如果刚好只有两个元素，出现同样次数，返回任何一个即可.