LeetCode_排序_简单_169.多数元素

这里写目录标题

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