LeetCode Majority Element【Easy】
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
解决
题目的意思是给定一个给定的数组中，找出多数的元素，假定数组长度为n，则这个多数元素定义为该元素在数组中出现的次数大于[n/2]次。
这里给出两种解决办法，代码和部分的注释如下。
hash法
/**
* 使用map key 存储数组，value 统计出现的次数
* @param nums
* @return
*/
public int majorityElement(int[] nums) {
Map<Integer,Integer> map = new HashMap<>();
int res =0;
for(int i:nums){
map.put(i,map.get(i)==null?1:map.get(i).intValue()+1);
if(map.get(i).intValue()>(nums.length/2)){
res=i;
}
}
return res;
}
数组方法
/**
* 排序，取数组mid，最后返回num[mid]值即为结果
* @param nums
* @return
*/
public int majorityElement2(int[] nums) {
Arrays.sort(nums);
int t = nums.length/2;
return nums[t];
}
