Leetcode(169) Majority Element

发表于 | 分类于

Description

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

1
2
Input: [3,2,3]
Output: 3

Example 2:

1
2
Input: [2,2,1,1,1,2,2]
Output: 2

解法

利用HashMap即可解决问题

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> helper = new HashMap<>();
        for (int i : nums) {
            if (helper.containsKey(i)) {
                helper.replace(i, helper.get(i) + 1);
            } else {
                helper.put(i, 1);
            }
        }
        int max = -1;
        int res = 0;
        for (Integer k : helper.keySet()) {
            res = helper.get(k) > max ? k : res;
            max = helper.get(k) > max ? helper.get(k) : max;
        }
        return res;
    }
}