剑指 Offer 39. 数组中出现次数超过一半的数字
难度:简单
方法一:哈希表统计法
遍历数组 nums,用 HashMap 统计各数字的数量,即可找出众数。此方法时间和空间复杂度均为 O(N)。
方法二:数组排序法
将数组 nums 排序,数组中点的元素一定为众数。
方法三:摩尔投票法
核心理念为票数正负抵消。此方法时间和空间复杂度分别为 O(N) 和 O(1),为本题的最佳解法。
详细如下:
设输入数组 nums 的众数为 x,数组长度为 n。
推论一:若记众数的票数为 +1,非众数的票数为 -1,则一定有所有数字的票数和 > 0。
推论二:若数组的前 a 个数字的票数和 = 0,则 数组剩余 (n-a) 个数字的票数和一定仍 >0,即后 (n-a) 个数字的众数仍为 x。
根据以上推论,记数组首个元素为 n1,众数为 x,遍历并统计票数。当发生票数和 = 0时,剩余数组的众数一定不变,这是由于:
- 当 n1 = x: 抵消的所有数字,有一半是众数 x。
- 当 n1 ≠ x: 抵消的所有数字,众数 x 的数量最少为 0 个,最多为一半。
利用此特性,每轮假设发生 票数和 = 0都可以缩小剩余数组区间。当遍历完成时,最后一轮假设的数字即为众数。
算法流程:
- 初始化:票数统计 votes = 0,众数 x;
- 循环:遍历数组 nums 中的每个数字 num;
- 当 票数 votes 等于 0,则假设当前数字 num 是众数;
- 当 num = x 时,票数 votes 自增 1;当 num != x 时,票数 votes 自减 1;
- 返回值:返回 x 即可;
class Solution {
public int majorityElement(int[] nums) {
int x = 0, votes = 0;
for(int num : nums){
if(votes == 0) x = num;
votes += num == x ? 1 : -1;
}
return x;
}
}
作者:Krahets
链接:https://leetcode.cn/leetbook/read/illustration-of-algorithm/99ussv/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
时间复杂度:O(N),空间复杂度:O(1)。
标签:votes,offer,票数,nums,num,数学,一刷,数组,众数 From: https://www.cnblogs.com/CWZhou/p/16838433.html