日拱算法：多數元素

持續創作，加速成長！這是我參與「掘金日新計劃 · 6 月更文挑戰」的第27天，點擊查看活動詳情

---

xixixi，更文無力，轉攻算法簡單題。中難題畏畏縮縮，簡單題我重拳出擊~~

突一突 LeetBook 列表/算法面試題彙總

沖沖衝~~

題目：### 多數元素

給定一個大小為 n 的數組 nums ，返回其中的多數元素。多數元素是指在數組中出現次數 大於 ⌊ n/2 ⌋ 的元素。

你可以假設數組是非空的，並且給定的數組總是存在多數元素。

示例 1：

輸入： nums = [3,2,3] 輸出： 3

示例 2：

輸入： nums = [2,2,1,1,1,2,2] 輸出： 2

提示：

• n == nums.length
• 1 <= n <= 5 * 104
• -109 <= nums[i] <= 109

解：

方法一：map 實現

通過一遍map，將所有出現元素和他們出現的次數進行存儲，因為map的唯一性，然後對其進行一次遍歷，找出最大值，第一次map操作時間複雜度為o(1),第二次而o(n),所以總體加起來為O(n); 但是由於開闢了一個map空間，空間複雜度同樣是o(n)

```js /* * @param {number[]} nums * @return {number} / var majorityElement = function(nums) { let map = new Map() for(let i=0;i<nums.length;i++){ if(map.has(nums[i])){ map.set(nums[i],map.get(nums[i])+1) }else{ map.set(nums[i],1) } }

for(let [key,val] of map.entries()){
    if(val>nums.length/2){
        return key
    }
}

}; ```

方法二：排序

思路：排序數組，如果有一個數字出現的頻率大於n/2，則在數組nums.length / 2的位置就是這個數

複雜度分析：時間複雜度：O(nlogn)，快排的時間複雜度。空間複雜度：O(logn)，排序需要logn的空間複雜度

js var majorityElement = function (nums) { nums.sort((a, b) => a - b); return nums[Math.floor(nums.length / 2)]; };

OK，以上便是本篇分享。點贊關注評論，為好文助力👍

我是掘金安東尼 🤠 100 萬閲讀量人氣前端技術博主 💥 INFP 寫作人格堅持 1000 日更文 ✍ 關注我，陪你一起度過漫長編程歲月 🌏