前端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 實(shí)現(xiàn)
通過一遍map，將所有出現(xiàn)元素和他們出現(xiàn)的次數(shù)進(jìn)行存儲，因?yàn)閙ap的唯一性，然后對其進(jìn)行一次遍歷，找出最大值，第一次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)];
};以上就是前端JavaScript多數(shù)元素的算法詳解的詳細(xì)內(nèi)容，更多關(guān)于JavaScript多數(shù)元素算法的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章主要為大家介紹了JS SVG獲取驗(yàn)證碼的玩法示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-07-07
微信小程序 input輸入及動態(tài)設(shè)置按鈕的實(shí)現(xiàn)
這篇文章主要介紹了微信小程序 input輸入及動態(tài)設(shè)置按鈕的實(shí)現(xiàn)的相關(guān)資料,希望通過本文能幫助到大家，需要的朋友可以參考下2017-10-10
這篇文章主要介紹了前端JavaScript多數(shù)元素的算法詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-07-07
await vs return vs return await關(guān)鍵區(qū)別
這篇文章主要為大家介紹了await vs return vs return await關(guān)鍵區(qū)別解析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-12-12
preload 顧名思義就是一種預(yù)加載的方式，它通過聲明向?yàn)g覽器聲明一個需要提交加載的資源，當(dāng)資源真正被使用的時候立即執(zhí)行，就無需等待網(wǎng)絡(luò)的消耗2020-02-02
些很實(shí)用且必用的小腳本代碼...2006-06-06
mui框架基于htm5plus的XMLHttpRequest，封裝了常用的Ajax函數(shù)。本文重點(diǎn)給大家介紹使用MUI框架模擬手機(jī)端的下拉刷新和上拉加載功能，感興趣的朋友參考下吧2017-09-09
這篇文章主要介紹了微信小程序 五星評分(包括半顆星評分)實(shí)例代碼的相關(guān)資料,需要的朋友可以參考下2016-12-12
JavaScript前端實(shí)用的工具函數(shù)封裝
這篇文章主要為大家介紹了JavaScript前端實(shí)用的一些工具函數(shù)的封裝，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-07-07
這篇文章主要為大家介紹了JavaScript 條件判斷使用技巧詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-09-09