前端JavaScript多数元素的算法详解

 更新时间:2022年07月09日 08:53:34   作者:掘金安东尼  
这篇文章主要介绍了前端JavaScript多数元素的算法详解,有需要的朋友可以借鉴参考下,希望能够有所帮助,祝大家多多进步,早日升职加薪
(福利推荐:【腾讯云】服务器最新限时优惠活动,云服务器1核2G仅99元/年、2核4G仅768元/3年,立即抢购>>>:9i0i.cn/qcloud

(福利推荐:你还在原价购买阿里云服务器?现在阿里云0.8折限时抢购活动来啦!4核8G企业云服务器仅2998元/3年,立即抢购>>>:9i0i.cn/aliyun

题目:多数元素

给定一个大小为 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多数元素算法的资料请关注程序员之家其它相关文章!

相关文章

  • JS微前端MicroApp基础使用

    JS微前端MicroApp基础使用

    这篇文章主要为大家介绍了JS微前端MicroApp基础使用,有需要的朋友可以借鉴参考下,希望能够有所帮助,祝大家多多进步,早日升职加薪
    2022-08-08
  • 微信小程序 地图map详解及简单实例

    微信小程序 地图map详解及简单实例

    这篇文章主要介绍了微信小程序 地图map详解及简单实例的相关资料,需要的朋友可以参考下
    2017-01-01
  • javascript对象3个属性特征

    javascript对象3个属性特征

    这篇文章主要介绍了javascript对象3个属性特征,writable可写、enumerable可枚举、configurable可配置,下面来看看文章的详细内容吧
    2021-11-11
  • 微信小程序 实现列表项滑动显示删除按钮的功能

    微信小程序 实现列表项滑动显示删除按钮的功能

    这篇文章主要介绍了微信小程序列表项滑动显示删除按钮的相关资料,需要的朋友可以参考下
    2017-04-04
  • 微信小程序 页面滑动事件的实例详解

    微信小程序 页面滑动事件的实例详解

    这篇文章主要介绍了微信小程序 页面滑动事件的实例详解的相关资料,希望通过本文能帮助到大家,让大家实现这样的功能,需要的朋友可以参考下
    2017-10-10
  • 微信小程序联网请求的轮播图

    微信小程序联网请求的轮播图

    这篇文章主要介绍了微信小程序联网请求的轮播图的相关资料,需要的朋友可以参考下
    2017-07-07
  • Three.js相机Camera控件知识梳理

    Three.js相机Camera控件知识梳理

    这篇文章主要为大家介绍了Three.js相机Camera控件知识梳理,有需要的朋友可以借鉴参考下,希望能够有所帮助,祝大家多多进步,早日升职加薪
    2023-05-05
  • 四十九个javascript小知识实用技巧

    四十九个javascript小知识实用技巧

    这篇文章主要给大家分享得是四十九个javascript小知识实用技巧像下面文章围绕JavaScript得各种技巧详细介绍,需要的朋友可以参考一下,希望对你有所帮助
    2021-11-11
  • JavaScript?ES新特性块级作用域

    JavaScript?ES新特性块级作用域

    这篇文章主要介绍了JavaScript?ES新特性块级作用域,所谓的块级作用域,就是该变量只能在声明时的代码块或者子代码块中使用,使JavaScript出现了块级作用域,具体详细内容请参考下面文章内容
    2021-12-12
  • 一看就懂的JavaScript适配器模式图解及使用示例

    一看就懂的JavaScript适配器模式图解及使用示例

    这篇文章主要为大家介绍了JavaScript适配器模式图解及使用示例分析,有需要的朋友可以借鉴参考下,希望能够有所帮助,祝大家多多进步,早日升职加薪
    2022-12-12

最新评论

?


http://www.vxiaotou.com