前端JavaScript多數元素的算法詳解

Posted on by

題目：多數元素

給定一個大小為 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)];
};

以上就是前端JavaScript多數元素的算法詳解的詳細內容，更多關於JavaScript多數元素算法的資料請關註WalkonNet其它相關文章！

推薦閱讀：