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

題目:多數元素

給定一個大小為 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其它相關文章!

推薦閱讀: