跳转至

169.多数元素

题目描述

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

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

示例 1:

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

示例 2:

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

题解

方法一：哈希表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
public int majorityElement(int[] nums) {
    Map<Integer,Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        if(map.containsKey(nums[i])){
            int count = map.get(nums[i]);
            count++;
            if(count>nums.length/2){
                return nums[i];
            }
            map.put(nums[i],count);
        }else{
            map.put(nums[i],1);
        }
    }
    return nums[0];
}

方法二：排序

1
2
3
4
public int majorityElement(int[] nums) {
    Arrays.sort(nums);
    return nums[nums.length/2];
}