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

目录
  • 题目：多数元素
  • 方法一：map 实现
  • 方法二：排序

题目：多数元素

给定一个大小为 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多数元素算法的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • 浅谈JavaScript构造树形结构的一种高效算法

    浅谈JavaScript构造树形结构的一种高效算法

    引言 我们经常会碰到树形数据结构,比如组织层级.省市县或者动植物分类等等数据.下面是一个树形结构的例子: 在实际应用中,比较常见的做法是将这些信息存储为下面的结构,特别是当存在1对多的父/子节点关系时: const data = [ { id: 56, parentId: 62 }, { id: 81, parentId: 80 }, { id: 74, parentId: null }, { id: 76, parentId: 80 }, { id: 63, parentId: 62 }, {

  • JavaScript数组排序的六种常见算法总结

    前言 着急用的话,选择前两个就行了,后面的看看就好. 开发中,遇到数组排序的需求很频繁,这篇文章会介绍几个常见排序思路. 一.希尔排序(性能最好) 如果要从大到小排列,则 while(arr[n] > arr[n - interval] && n > 0) . // 希尔排序算法 function xier(arr){ var interval = parseInt(arr.length / 2);//分组间隔设置 while(interval > 0){ for(var

  • Js Snowflake(雪花算法)生成随机ID的实现方法

    Js Snowflake(雪花算法)生成随机ID的实现方法

    1.snowflake-id插件 import SnowflakeId from "snowflake-id"; const guid = num => { const id= new SnowflakeId(); return id.generate(); }; 2.原生使用 var Snowflake = /** @class */ (function() { function Snowflake(_workerId, _dataCenterId, _sequence) {

  • 利用JS实现二叉树遍历算法实例代码

    利用JS实现二叉树遍历算法实例代码

    目录 前言 一.二叉树 1.1.遍历二叉树 1.2.用js表示二叉树 1.3.前序遍历算法 1.4.中序遍历算法 1.5.后序遍历算法 1.6.按层遍历算法 二.算法题 1.1.二叉树的最大深度 1.2.二叉树的所有路径 总结 前言 在计算机科学中, 树(tree) 是一种广泛使用的抽象数据类型(ADT),是一类非线性数据结构.树在计算机领域得到广泛应用,尤其二叉树最为常用. 树的相关概念: 结点:每个元素称为结点 树根:根节点 度:一个结点含有的子结点的个数称为该结点的度 叶子节点:度为0的节

  • JS中多层次排序算法的实现代码

    JS中多层次排序算法的实现代码

    引子 排序在编程中随处可见,从开始学习变成,到项目开发,基本上或多或少会遇到一些排序问题,接下来我要写的是我在实际开发终于到的一个排序问题,一开始卡了我很久,后面随着知识积累,实践变多才解决掉了,不知道是不是我搜索关键字不对,还是其他原因,百度也没有找到这方面的内容. 数据结构和需求 var arr = [ { "soNumber" : "52085848", "item" : "313281", "amount&q

  • Vue中使用crypto-js AES对称加密算法实现加密解密

    Vue中使用crypto-js AES对称加密算法实现加密解密

    目录 下载crypto-js 加密解密数据 AES算法的ECB模式加密-设置秘钥 AES算法的CBC模式加密-设置秘钥和偏移量 参考: 在数字加密算法中,通过可划分为对称加密和非对称加密 对称加密:如AES,DES,3DES 含义:加密和解密使用的是同一把钥匙.密钥不能在网络中传输,避免被拦截.如果要传输,必须要对密钥进行非对称加密再加密一次. 优点:算法简单,加密解密容易,效率高,执行快. 缺点:相对来说不算特别安全,只有一把钥匙,密文如果被拦截,且密钥也被劫持,那么,信息很容易被破译. 非对

  • JS算法教程之字符串去重与字符串反转

    一.字符串去重 说起字符串去重,第一时间就会想起数组去重,所以我们可以把字符串转换为数组,然后对数组去重,去重完毕后在拼接成字符串,下面就简单罗列两种字符串去重的方法,接下来我们看代码. 第一种方法: 逻辑步骤: 1.使用split或者ES6的展开运算符...把字符串切割成数组 2.使用ES6的Set数据解构,它类似于数组,但是它成员的值都是唯一的,使用new创建 3.对去重后的数组使用join拼接 let str = '11223344aabbcc' function strSeparate(

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

    目录 题目:多数元素 方法一:map 实现 方法二:排序 题目:多数元素 给定一个大小为 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

  • JavaScript DOM元素常见操作详解【添加、删除、修改等】

    本文实例讲述了JavaScript DOM元素常见操作.分享给大家供大家参考,具体如下: DOM概念 DOM(Document Object Model):文档对象模型. 通过开发者工具的Elements标签页可以查看 通过开发者工具的Sources标签页也可以观察到整个文档是有一系列节点 整个文档是由一系列节点对象组成的一棵树. 节点(Node)包括元素节点(1).属性节点(2).文本节点(3)(1..2..3..代表节点类型)_ var th1= document.getElementByI

  • 微前端之 js隔离 样式隔离 元素隔离问题详解

    微前端之 js隔离 样式隔离 元素隔离问题详解

    目录 WebComponent 介绍 js隔离 问题 解决 方法一用 Proxy 代理 方法二 用快照 样式隔离 问题 方法一 样式增加不同前缀 方法二 ShadawDom 元素隔离 WebComponent 介绍 微前端框架中,js隔离.样式隔离.元素隔离是必须解决的三个问题,下面我们就来分别说说这三个问题是什么?怎么解决? 涉及的核心点是 Proxy,WebComponent,shadowDOM WebComponent 不在这三个问题中,但是我们做个简单介绍 浏览器默认的标签有 div,a

  • 从表单校验看JavaScript策略模式的使用详解

    众所周知的是,表单确实在前端,唔,或者说在网页中占有不小的比重.事实上,几乎每一个中大型网站都会有"登录注册"以验证用户信息.防止一些不可名状的隐患... 那么表单的优劣就成了前端开发者急需解决的问题.其实我更愿意称为"代码的可读性"或"可复用性"以及"是否冗杂". 表单也有"优劣"?你在开玩笑嘛? 我想你可以认真看下下面的代码,它用到了一些"新知识": <form action=

  • JavaScript编写棋盘覆盖代码详解

    JavaScript编写棋盘覆盖代码详解

    一.前言 之前做了一个算法作业,叫做棋盘覆盖,本来需要用c语言来编写的,但是因为我的c语言是半桶水(哈哈),所以索性就把网上的c语言写法改成JavaScript写法,并且把它的覆盖效果显示出来 二.关键代码 <!DOCTYPE html> <html> <head><meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <titl

  • Js面试算法详解

    素数 Q:你将如何验证一个素数? A:一个素数只能被它自己和1整除.所以,我将运行一个while循环并加1.(看代码示例,如果你无法理解,那这不是你的菜.先回去学习javaScript基础知识然后再回来吧.) 方法1 function isPrime(n){ var divisor = 2; while (n > divisor){ if(n % divisor == 0){ return false; } else divisor++; } return true; } isPrime(137

  • javascript中Array()数组函数详解

    在程序语言中数组的重要性不言而喻,JavaScript中数组也是最常使用的对象之一,数组是值的有序集合,由于弱类型的原因,JavaScript中数组十分灵活.强大,不像是Java等强类型高级语言数组只能存放同一类型或其子类型元素,JavaScript在同一个数组中可以存放多种类型的元素,而且是长度也是可以动态调整的,可以随着数据增加或减少自动对数组长度做更改. Array()是一个用来构建数组的内建构造器函数.数组主要由如下三种创建方式: array = new Array() array =

  • python实现决策树C4.5算法详解(在ID3基础上改进)

    python实现决策树C4.5算法详解(在ID3基础上改进)

    一.概论 C4.5主要是在ID3的基础上改进,ID3选择(属性)树节点是选择信息增益值最大的属性作为节点.而C4.5引入了新概念"信息增益率",C4.5是选择信息增益率最大的属性作为树节点. 二.信息增益 以上公式是求信息增益率(ID3的知识点) 三.信息增益率 信息增益率是在求出信息增益值在除以. 例如下面公式为求属性为"outlook"的值: 四.C4.5的完整代码 from numpy import * from scipy import * from mat

  • Javascript 严格模式use strict详解

    严格模式:由ECMA-262规范定义的JavaScript标准,对javascrip的限制更强. (非严格的模式,被称为"马虎模式/稀松模式/懒散模式".) 一.严格模式的使用 严格模式可以在脚本或函数级别实现.(即全局和局部模式) 1.全局 在js文件的最前面添加    "use strict" 2.局部 在函数内部添加   "use strict",如下 function fn() { "use strict"; //so

  • JavaScript数据类型的存储方法详解

    JavaScript数据类型的存储方法详解

    一个很基础的知识点,JavaScript中基本数据类型和引用数据类型是如何存储的. 由于自己是野生程序员,在刚开始学习程序设计的时候没有在意内存这些基础知识,导致后来在提到"什么什么是存在栈中的,栈中只是存了一个引用"这样的话时总是一脸懵逼.. 后来渐渐的了解了一些内存的知识,这部分还是非常有必要了解的. 基本数据结构 栈 栈,只允许在一段进行插入或者删除操作的线性表,是一种先进后出的数据结构. 堆 堆是基于散列算法的数据结构. 队列 队列是一种先进先出(FIFO)的数据结构. Jav

随机推荐