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

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

题目

169. 求众数

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ 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;                     
};