日拱算法：多數元素

持續創作，加速成長！這是我參與「掘金日新計劃 · 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)

/**
 * @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

的空間複雜度

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

複制

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

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