有人相爱，有人夜里开车看海，我是leetcode第一题都做不出来

这是LeetCode的第169题：多数元素

难度属于简单类型

多数元素

给定一个大小为 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