前端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其它相關文章!
推薦閱讀:
- 前端JavaScript算法找出隻出現一次的數字
- C++LeetCode數據結構基礎詳解
- Java算法練習題,每天進步一點點(2)
- Go&java算法之最大數示例詳解
- 詳解Java中二分法的基本思路和實現