问题描述
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:
Input: [3,2,3] Output: 3 Example 2:
Input: [2,2,1,1,1,2,2] Output: 2
解决思路
用HashMap将num和count以键值对的形式进行存储吗，count用来记录num出现的次数，符合要求的就return
代码
package leetcode;
import java.util.HashMap;
import java.util.Map;
public class MajorityElement {
public int majorityElement(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
//getting times of elements that occured in nums and process that
for (int num : nums) {
Integer count = map.get(num);
if (count == null){
count = 1;//num occurs for the first time
}else{
count++;//num has been counted before
}
//storing num and count as the form of Key-Value in HashMap
map.put(num, count);
if (map.get(num) > (nums.length / 2)){
return num;
}
}
return 0;
}
}
