欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

前端JavaScript多數(shù)元素的算法詳解

 更新時(shí)間：2022年07月09日 08:53:34   作者：掘金安東尼  
這篇文章主要介紹了前端JavaScript多數(shù)元素的算法詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

題目：多數(shù)元素

給定一個(gè)大小為 n 的數(shù)組 nums ，返回其中的多數(shù)元素。多數(shù)元素是指在數(shù)組中出現(xiàn)次數(shù) 大于 ⌊ n/2 ⌋ 的元素。

你可以假設(shè)數(shù)組是非空的，并且給定的數(shù)組總是存在多數(shù)元素。

  示例 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 實(shí)現(xiàn)

通過一遍map，將所有出現(xiàn)元素和他們出現(xiàn)的次數(shù)進(jìn)行存儲(chǔ)，因?yàn)閙ap的唯一性，然后對其進(jìn)行一次遍歷，找出最大值，第一次map操作時(shí)間復(fù)雜度為o(1),第二次而o(n),所以總體加起來為O(n); 但是由于開辟了一個(gè)map空間，空間復(fù)雜度同樣是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
        }
    }
};

方法二：排序

思路：排序數(shù)組，如果有一個(gè)數(shù)字出現(xiàn)的頻率大于n/2，則在數(shù)組nums.length / 2的位置就是這個(gè)數(shù)

復(fù)雜度分析：時(shí)間復(fù)雜度：O(nlogn)，快排的時(shí)間復(fù)雜度?？臻g復(fù)雜度：O(logn)，排序需要logn的空間復(fù)雜度

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

以上就是前端JavaScript多數(shù)元素的算法詳解的詳細(xì)內(nèi)容，更多關(guān)于JavaScript多數(shù)元素算法的資料請關(guān)注腳本之家其它相關(guān)文章！

相關(guān)文章

最新評(píng)論