问题
Given an array nums of size n, return the majority element.The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
Boyer-Moore投票算法
基本思想:
众数的值为+1,非众数的值为-1。其加和作为投票值。
遍历整个数组,由于众数数量大于非众数,因此最后结果一定为正数。
设置count记录票数,遍历数组。
当count为0时,则将当前的数组设为众数。当之后的数字与其相等,则count+1,反之则-1。
遍历完成后返回当前的众数。
根据以上规则,每次我们选择的众数,都是已遍历数组范围内出现最多次数的数值之一。
由于给定的数组的众数超过半数,因此遍历到最后的众数,一定是整个数组中出现最多次的数值。
核心就是对拼消耗。
玩一个诸侯争霸的游戏,假设你方人口超过总人口一半以上,并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。那就大混战呗,最差所有人都联合起来对付你(对应你每次选择作为计数器的数都是众数),或者其他国家也会相互攻击(会选择其他数作为计数器的数),但是只要你们不要内斗,最后肯定你赢。
最后能剩下的必定是自己人。
1 | class Solution { |
遍历数组,并将各个数值出现的次数记录在哈希表中。
当出现的次数大于数组的一半,则该数值是众数。
1 | class Solution { |