天天看点

LeetCode_排序_简单_169.多数元素1.题目2.思路3.代码实现(Java)

这里写目录标题

  • 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;
}