前端JavaScript多數(shù)元素的算法實例分析

這篇文章主要介紹“前端JavaScript多數(shù)元素的算法實例分析”的相關(guān)知識，小編通過實際案例向大家展示操作過程，操作方法簡單快捷，實用性強，希望這篇“前端JavaScript多數(shù)元素的算法實例分析”文章能幫助大家解決問題。

題目：多數(shù)元素

給定一個大小為 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 實現(xiàn)

通過一遍map，將所有出現(xiàn)元素和他們出現(xiàn)的次數(shù)進行存儲，因為map的唯一性，然后對其進行一次遍歷，找出最大值，第一次map操作時間復(fù)雜度為o(1),第二次而o(n),所以總體加起來為O(n); 但是由于開辟了一個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ù)組，如果有一個數(shù)字出現(xiàn)的頻率大于n/2，則在數(shù)組nums.length / 2的位置就是這個數(shù)

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

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

關(guān)于“前端JavaScript多數(shù)元素的算法實例分析”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識，可以關(guān)注億速云行業(yè)資訊頻道，小編每天都會為大家更新不同的知識點。