| 算法

算法---多数元素

“ 今日分享Leetcode上面一道简单的算法，它就是编号169—多数元素。”

1. 多数元素—方法一

首先老规矩，先放题目，如下图所示：

多数元素

多数元素题目图

首先说一下思路一：需要注意题目中说的”多数元素是指在数组中出现次数大于n/2”，由这句话翻译过来就表示：出现次数最多的数一定超过长度的一半。接下来我需要画图说明，如下图一所示：
解析思路图一
解析思路图一

可能图一看的有点云里雾里的，但是请结合图一，我接下来举一个实例来解释图一什么意思，假设输入的值为：[2,1,1,1,1,2,2]，如下图二所示：
解析思路图二
解析思路图二

在看了上面两幅图之后，总结一下步骤：
对数组进行排序；

取排序之后中间值(即：Math.floor(n/2))的下标就是数组中出现次数大于n/2的元素。

代码如下所示：

1
2
3
4
5
6
7
8
/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    nums.sort((a,b)=> a-b);
    return nums[Math.floor(nums.length/2)]
};

2. 多数元素—方法二

方法一中运行时间和内存会比较大，因此接下来介绍一下方法二的方法，其实就是利用Map对象来实现的，利用Map对象的key和value来映射关系，key表示元素，value表示元素出现的次数，定义一个存储出现次数最多的max变量，最后通过在map对象中找到max值所对应的key，该key即是出现次数大于n/2的元素。
代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let map = new Map();
    const len = nums.length;
    let count = 1;
    let max = 0;
    for (let i = 0; i < len ;i++) {
        if (map.has(nums[i])) {
            count = map.get(nums[i]) + 1;
        } else {
            count = 1;
        }
        map.set(nums[i], count);
        max = Math.max(map.get(nums[i]), max);
    }
    for (let [key, value] of map.entries()) {
        if (value === max) return key;
    } 
};

如果对Map对象不是很清楚的朋友可以去看看mdn上面的介绍和一些demo。

参考链接：mdn文档下Map对象使用