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