LeetCode—剑指Offer：数组中出现次数超过一半的数字（排序+投票）数组中出现次数超过一半的数字（简单）

75 阅读 0 评论 50 点赞

我是靠谱客的博主自由小懒猪，这篇文章主要介绍LeetCode—剑指Offer：数组中出现次数超过一半的数字（排序+投票）数组中出现次数超过一半的数字（简单），现在分享给大家，希望可以做个参考。

数组中出现次数超过一半的数字（简单）

2020年9月3日

题目来源：力扣

在这里插入图片描述

解题

这道题与多数元素一样，可参考

排序
出现次数超过一半，那排序后的中位数肯定是它

class Solution {
    public int majorityElement(int[] nums) {
        //先从小到大排序
        Arrays.sort(nums);
        //找中位数
        return nums[nums.length/2];
    }
}

在这里插入图片描述

摩尔投票法
因为出现次数超过一半，支持这个数的肯定会大于0

class Solution {
    public int majorityElement(int[] nums) {
        int x=0,votes=0;
        for(int num:nums){
            //如果票数为0，那么取下个数值为投票的数
            if(votes==0) x=num;
            //计票数，支持它的就加一，不支持就减一
            votes+=num==x?1:-1;
        }
        //最后返回投票的数
        return x;
    }
}