题目

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

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

示例1：

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

示例2：

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

思路 + 代码

法1. 我的方法，超笨。用一个Map记录数字出现的次数，然后当次数大于n/2时返回。

代码

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int len = nums.length;
        for(int i=0; i<len; i++){
            if(map.get(nums[i])!=null){
                Integer num = map.get(nums[i]);
                map.put(nums[i], num+1);
            }else{
                map.put(nums[i], 1);
            }
            if(map.get(nums[i])>len/2)  return nums[i];
        }
        return 0;
    }
}

法2. 先排序，后取中位数

代码略

法3. 用一个变量count计数，从0开始，遇到相同的+1，遇到不同的-1，变为零则重新计数。

代码

class Solution {
    public int majorityElement(int[] nums) {
        int count = 1;
        int len = nums.length;
        int num = nums[0];
        for(int i=1; i<len; i++){
            if(num==nums[i]) count++;
            else count--;
            if(count==0) {
                num = nums[i];
                count = 1;
            }
        }
        return num;
    }
}