前端JavaScript多數(shù)元素的算法詳解
更新時間：2022年07月09日 08:53:34 作者：掘金安東尼
這篇文章主要介紹了前端JavaScript多數(shù)元素的算法詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪
題目：多數(shù)元素
給定一個大小為 n 的數(shù)組 nums ，返回其中的多數(shù)元素。多數(shù)元素是指在數(shù)組中出現(xiàn)次數(shù) 大于 ⌊ n/2 ⌋ 的元素。
你可以假設數(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操作時間復雜度為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
}
}
};
方法二：排序
思路：排序數(shù)組，如果有一個數(shù)字出現(xiàn)的頻率大于n/2，則在數(shù)組nums.length / 2的位置就是這個數(shù)
復雜度分析：時間復雜度：O(nlogn)，快排的時間復雜度?？臻g復雜度：O(logn)，排序需要logn的空間復雜度
var majorityElement = function (nums) {
nums.sort((a, b) => a - b);
return nums[Math.floor(nums.length / 2)];
};以上就是前端JavaScript多數(shù)元素的算法詳解的詳細內容，更多關于JavaScript多數(shù)元素算法的資料請關注腳本之家其它相關文章！
相關文章
這篇文章主要為大家介紹了JS微前端MicroApp基礎使用，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-08-08
這篇文章主要介紹了微信小程序 地圖map詳解及簡單實例的相關資料,需要的朋友可以參考下2017-01-01
這篇文章主要介紹了javascript對象3個屬性特征，writable可寫、enumerable可枚舉、configurable可配置，下面來看看文章的詳細內容吧2021-11-11
這篇文章主要介紹了微信小程序列表項滑動顯示刪除按鈕的相關資料,需要的朋友可以參考下2017-04-04
這篇文章主要介紹了微信小程序 頁面滑動事件的實例詳解的相關資料,希望通過本文能幫助到大家，讓大家實現(xiàn)這樣的功能，需要的朋友可以參考下2017-10-10
這篇文章主要介紹了微信小程序聯(lián)網(wǎng)請求的輪播圖的相關資料,需要的朋友可以參考下2017-07-07
這篇文章主要為大家介紹了Three.js相機Camera控件知識梳理，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-05-05
這篇文章主要給大家分享得是四十九個javascript小知識實用技巧像下面文章圍繞JavaScript得各種技巧詳細介紹,需要的朋友可以參考一下，希望對你有所幫助2021-11-11
這篇文章主要介紹了JavaScript?ES新特性塊級作用域，所謂的塊級作用域，就是該變量只能在聲明時的代碼塊或者子代碼塊中使用，使JavaScript出現(xiàn)了塊級作用域，具體詳細內容請參考下面文章內容2021-12-12
這篇文章主要為大家介紹了JavaScript適配器模式圖解及使用示例分析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-12-12