3
日拱算法：多数元素_安东尼漫长的技术岁月的技术博客_51CTO博客
source link: https://blog.51cto.com/u_13961087/5429208
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
日拱算法：多数元素
原创突一突 LeetBook 列表/算法面试题汇总
冲冲冲~~
题目：### 多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入： nums = [3,2,3]
输出： 3
输出： 3
示例 2：
输入： nums = [2,2,1,1,1,2,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
}
}
};
* @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)];
};
nums.sort((a, b) => a - b);
return nums[Math.floor(nums.length / 2)];
};
OK，以上便是本篇分享。点赞关注评论，为好文助力👍
我是掘金安东尼 🤠 100 万阅读量人气前端技术博主 💥 INFP 写作人格坚持 1000 日更文 ✍ 关注我，陪你一起度过漫长编程岁月 🌏
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK