著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
这道题也是《剑指offer》原题——面试题39数组中出现次数超过一半的数字。
给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
使用哈希表的思路:用数字作为key,每遇到一次,值加一。遍历完数字后,找出次数最大的。
思路很简单,时间复杂度O(N),空间复杂度O(N),N表示哈希表槽大小。
摩尔投票法的核心思想:因为元素出现次数超过一半,所以它出现的次数减去剩余元素出现次数一定是大于0的。基于这个思想,可以使用抵消的办法来消除掉所有非目标元素,然后剩下的就是目标元素了。
可以先随机找一个元素作为标杆,然后往后遍历,这个标杆元素每出现一次,次数加一。只要出现非标杆元素,次数减一。当次数变成0后,重新设置标杆元素,重复上面的过程。直到最后剩下来的元素就是目标元素。
以target表示目标元素,count表示出现的次数。过程描述:
最后剩下来的目标元素是7,也就是我们需要的值。