多数元素
给定一个大小为 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) } } };
知识点
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