【Leetcode】【简单】【169求众数】【JavaScript…

2019-03-10 11:50:34来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

 

题目

169. 求众数

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

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

示例 1:

输入: [3,2,3]
输出: 3

示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

 

众数(Mode)是统计学名词,在统计分布上具有明显集中趋势点的数值,代表数据的一般水平(众数可以不存在或多于一个)。 修正定义:是一组数据中出现次数最多的数值,叫众数,有时众数在一组数中有好几个。用 M 表示。 理性理解:简单的说,就是一组数据中占比例最多的那个数。--《百度百科》

 

解答

解答一、对象中存储所有元素及出现次数

拿到题目,我的第一想法就是for循环,

使用for循环遍历元素并记下每个元素出现的次数,

存储在一个对象中。

 

代码如下:(leetcode已提交通过,执行用时:128ms)


/**
*未考虑nums数组元素个数为偶数的情况
*未考虑存在多个众数的情况
*未考虑不存在众数的情况
*未考虑数组中存在非数字的情况
*/

var majorityElement = function(nums) {
    var obj={};                         
    var halfNum=nums.length/2;
    var mode;
    if (nums.length===1) return nums[0];
    for (let i=0;i<nums.length;i++){    //拆解数组中元素,赋值为对象的key
       if(obj[nums[i]]){                //遍历,若已有该key,
           obj[nums[i]]+=1;             //对应的value+1
           if(obj[nums[i]]>halfNum){    //若该key对应的value大于数组元素个数的半数
                mode=nums[i];
                return mode;            //返回该key值
           }
       }else{
           obj[nums[i]]=1;              //若没有,加key,对应value赋值为1
       }
    }
};

 

解答二、假设法

for of 遍历,假设第一个数为众数,count计1,
其后的数字若相同则count 加1,否则count减1,
当count减为0时,假设此时新的num为众数,继续判断,
众数出现次数始终大于或等于所有元素个数的一半,
如果存在众数,最终一定存在一个num,使得count大于0,
!!缺点:若不存在众数,则会返回最后一个元素。

 

代码如下:(leetcode已提交通过,执行用时:104ms)

let majorityElement = function(nums) {
    let count = 0;
    let mode = 0;
    for (let num of nums) {          
        if (count === 0) {            
            mode = num;               
        }                            
        count = mode === num ? count + 1 : count - 1;
    }                                 
    return mode;                     
};  

 


原文链接:https://www.cnblogs.com/2463901520-sunda/p/10489540.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:js三部曲---预编译

下一篇:layui-时间选择器-时间范围选择