剑指 Offer 39. 数组中出现次数超过一半的数字


剑指 Offer 39. 数组中出现次数超过一半的数字

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;
    }

     public int majorityElement2(int[] nums) {
        int x = 0, votes = 0, count = 0;
        for(int num : nums){
            if(votes == 0) x = num;
            votes += num == x ? 1 : -1;
        }
        // 验证 x 是否为众数
        for(int num : nums)
            if(num == x) count++;
        return count > nums.length / 2 ? x : 0; // 当无众数时返回 0
    }
// 作者:jyd
// 链接:https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/solution/mian-shi-ti-39-shu-zu-zhong-chu-xian-ci-shu-chao-3/
}

本题常见的三种解法:

哈希表统计法: 遍历数组 nums ,用 HashMap 统计各数字的数量,即可找出众数 。时间和空间复杂度 O(N) 。
数组排序法: 将数组 nums 排序,数组中点的元素 一定为众数。
摩尔投票法: 核心理念为 票数正负抵消 。此方法时间和空间复杂度分别为 O(N) 和 O(1) ,为本题的最佳解法。
摩尔投票法:
设输入数组 nums 的众数为 x ,数组长度为 n 。

推论一: 若记 众数 的票数为 +1 ,非众数 的票数为 −1 ,则一定有所有数字的 票数和 >0 。

推论二: 若数组的前 a 个数字的 票数和 =0 ,则 数组剩余
(n−a) 个数字的 票数和一定仍 >0 ,即后 (n−a) 个数字的 众数仍为 x。


文章作者:   future
版权声明:   本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 future !
 上一篇
剑指 Offer 53 - I. 在排序数组中查找数字 I 剑指 Offer 53 - I. 在排序数组中查找数字 I
剑指 Offer 53 - I. 在排序数组中查找数字 I统计一个数字在排序数组中出现的次数。 示例 1:输入: nums = [5,7,7,8,8,10], target = 8 输出: 2 示例 2: 输入: nums = [5,7,7
2021-02-27 future
下一篇 
628. 三个数的最大乘积 628. 三个数的最大乘积
628. 三个数的最大乘积class Solution { public int maximumProduct(int[] nums) { Arrays.sort(nums);
2021-02-27 future
  目录