剑指 Offer 39. 数组中出现次数超过一半的数字

短命女 2023-01-02 08:22 107阅读 0赞

故心故心故心故心小故冲啊

--------------------

### 文章目录 ###

*  题目: 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字,你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 *  解法一:sort+Math.floor
 *  解法二:map

--------------------

# 题目: 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字,你可以假设数组是非空的，并且给定的数组总是存在多数元素。 #

示例 1:  
输入: \[1, 2, 3, 2, 2, 2, 5, 4, 2\]  
输出: 2

限制：  
1 <= 数组长度 <= 50000

# 解法一:sort+Math.floor #

由题意可知 一个数字出现的次数超过数组长度的一半,所以在排序后,这个数字肯定是在中间的

var majorityElement = function(nums) { 
        var num  = nums.sort((a,b)=>a-b)
        return num[Math.floor(num.length/2)]
    };

![在这里插入图片描述][20210105121108423.png]

# 解法二:map #

var majorityElement = function(nums) { 
        var map = new Map();
        for(let key of nums){ 
            //通过键获取值,每次找到相同的键都会在最后+1并加入map
            let times = (map.get(key) || 0) + 1
            if(times >= nums.length/2)return key
            map.set(key,times)
    
        }
    };

![在这里插入图片描述][20210105122438678.png]

[20210105121108423.png]: /images/20221120/f9b98bc872fb496ba2f3b5481757bc02.png
[20210105122438678.png]: /images/20221120/937a4f6838584e8a83b4d21250a5342b.png