leetcode题 求众数

求众数
给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的,并且给定的数组总是存在众数。

示例 1:

输入: [3,2,3]
输出: 3
示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

首先看题目,给了一个大小为n的数组,然后找里面的众数。众数上面也说了,就是在数组中出现的次数要大于1/2。既然大于1/2,那么就有这么个性质,众数减去其他非众数的值大于等于1。根据这个性质,我们可以采用摩尔投票法。具体处理如下:

class Solution {
    public int majorityElement(int[] nums) {
        int label = nums[0],count = 0;
        for(int i = 0;i < nums.length;i ++){
            if(label == nums[i]){
                count++;
            }else{
                if(count == 0){
                    label = nums[i];
                }else{
                    count --;
                }
            }
            //System.out.println(count);
        }
        return label;
    }
}
Last modification:September 20th, 2019 at 07:27 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment