这里写目录标题
- 1.题目
- 2.思路
- 3.代码实现(Java)
1.题目
给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例 1:
输入:[3,2,3]
输出:3
示例 2:
输入:[2,2,1,1,1,2,2]
输出:2
进阶:
尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/majority-element
2.思路
(1)排序
将数组nums中的所有元素排序后(无论是升序还是降序),那么下标为⌊ n/2 ⌋的元素一定是众数。
(2)哈希表
(2.1)使用哈希表来存储每个元素以及出现的次数,其中键为元素,值为该元素出现的次数;
(2.2)遍历数组 nums 并将数组中的每个元素加入哈希表中;
(2.3)遍历哈希映射中的所有键值对,返回值最大的键即可。
3.代码实现(Java)
//(1)排序
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
//(2)哈希表
public int majorityElement(int[] nums) {
Map<Integer,Integer> hashMap=new HashMap<Integer,Integer>();
for(int i=0;i<nums.length;i++){
if(hashMap.containsKey(nums[i])){
hashMap.put(nums[i],hashMap.get(nums[i])+1);
}else{
hashMap.put(nums[i],1);
}
}
int cnt=1,elem=nums[0];
for (Integer key : hashMap.keySet()){
int tmpVal=hashMap.get(key);
if(tmpVal>cnt){
cnt=tmpVal;
elem=key;
}
}
return elem;
}