LeetCode多数元素使用JavaScript解题|前端学算法

简介: LeetCode多数元素使用JavaScript解题|前端学算法

多数元素


给定一个大小为 n 的数组 nums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的,并且给定的数组总是存在多数元素。

示例 1:

输入: nums = [3,2,3]

输出: 3

示例 2:

输入: nums = [2,2,1,1,1,2,2]

输出: 2


解题思路


题目要求:尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

所以考虑可以用map存储数据,把当前元素nums[i]当做key,出现的次数当做value,判断当前元素是否存在于map数据结构中,如果不存在则把他存储进去,并且初始值设为1,;如果存在则进行累加,且判断一下是否大于 nums.length/2,如果是则返回map值

具体步骤如下:

  • 第一步:初始化一个newMap
  • 第二步:判断一下nums长度,如果长度等于1则返回nums[0]
  • 第三步:遍历nums,判断newMap里面是否已经有nums[i],如果没有,则初始化值为1,;如果有,则进行累加,且判断一下是否大于 nums.length/2,如果是则返回当前值
var majorityElement = function(nums) {
    let newMap = new Map()
    if(nums.length === 1) return nums[0]
    for(let i=0;i<nums.length;i++){
        if(newMap.has(nums[i])){
            newMap.set(nums[i],newMap.get(nums[i])+1)
            if(newMap.get(nums[i])> nums.length/2){
                return nums[i]
            }
        }else{
             newMap.set(nums[i],1)
        }
    }
};


image.png


知识点


  • Map:对象保存键值对,并且能够记住键的原始插入顺序
// 初始化 Map
const contacts = new Map()
// 存储 键 值
contacts.set('Jessie', {phone: "213-555-1234", address: "123 N 1st Ave"})
// 判断map里是否有这个键
contacts.has('Jessie') // true
// 获取这个键(没有这个键的情况)
contacts.get('Hilary') // undefined
// 获取这个键(有这个键的情况)
contacts.get('Jessie') // {phone: "213-555-1234", address: "123 N 1st Ave"}
// 删除这个键(没有这个键的情况)
contacts.delete('Raymond') // false
// 删除这个键(有这个键的情况)
contacts.delete('Jessie') // true
// map的长度
console.log(contacts.size) // 1


目录
相关文章
|
14天前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
30 1
|
20天前
【LeetCode 27】347.前k个高频元素
【LeetCode 27】347.前k个高频元素
28 0
|
13天前
|
JavaScript 前端开发 应用服务中间件
vue前端开发中,通过vue.config.js配置和nginx配置,实现多个入口文件的实现方法
vue前端开发中,通过vue.config.js配置和nginx配置,实现多个入口文件的实现方法
83 0
|
13天前
|
移动开发 算法 前端开发
前端常用算法全解:特征梳理、复杂度比较、分类解读与示例展示
前端常用算法全解:特征梳理、复杂度比较、分类解读与示例展示
15 0
|
13天前
|
前端开发 JavaScript 程序员
【从前端入门到全栈】Node.js 之核心概念
【从前端入门到全栈】Node.js 之核心概念
|
21天前
【LeetCode 06】203.移除链表元素
【LeetCode 06】203.移除链表元素
27 0
|
21天前
【LeetCode-每日一题】移除元素
【LeetCode-每日一题】移除元素
29 0
|
27天前
|
JavaScript 前端开发 API
【前端基础篇】JavaScript之jQuery介绍
【前端基础篇】JavaScript之jQuery介绍
48 0
|
27天前
|
JavaScript 前端开发 Java
【前端基础篇】JavaScript之BOM介绍
【前端基础篇】JavaScript之BOM介绍
30 0
|
27天前
|
JavaScript 前端开发 UED
【前端基础篇】JavaScript之DOM介绍2
【前端基础篇】JavaScript之DOM介绍
20 0