剑指offer-js 数组中出现次数超过一半的数字

数组中出现次数超过一半的数字

JS中的Map对象

1，js创建map对象
	var map = new Map();
2.将键值对放入map对象
	map.set("key",value)
3.根据key获取map值
	map.get(key)
4.删除map指定对象
	delete map[key]	或	map.delete(key)
5.循环遍历map
	map.forEach(function(key){
	　　console.log("key",key)  //输出的是map中的value值
	})

题目描述：

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。
由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
如果不存在则输出0。

问题分析：

两种方式：
	1，利用js Map() 对象，通过是否存在进行计数，然后遍历，判断次数大小
	2，利用只有一个最大的特性，遍历整个数组，记录次数和当前值，通过前后是否相等进行比较
	如果相等则对次数加一，遍历结束，剩下一个当前值，最后根据当前值进行数组遍历，记录次数进行比较

代码展示：

function MoreThanHalfNum_Solution(numbers)
{
    //1，用map写，如果一个数不在map中，就加上，如果在，就+1，最后遍历找出最大的
    const len = numbers.length;
    if (len === 0) 
        return 0;
    
    var map = new Map();
    for (let i of numbers) {
        if (map.get(i) === undefined) {
            map.set(i, 1);
        }else {
            map.set(i, map.get(i)+1);
        }
    }
    // 或者 map.entries() 都可以，向下取整
    for (let item of map) {
        if (item[1] > Math.floor(len/2)) 
            return item[0];
    }
    return 0;

    //2，利用只有一个最大的特性，遍历整个数组，记录次数和当前值，通过前后是否相等进行比较
    // 如果相等则对次数加一，遍历结束，剩下一个当前值，最后根据当前值进行数组遍历，记录次数进行比较
    if (numbers.length === 0) 
    	return 0;
    let res = numbers[0];
    let times = 1;
    for (let i of numbers) {
        if (times === 0) {
            res = i;
            times = 1;
        }
        else if (i === res) 
        	times++;
        else 
        	times--;
    }
    times = 0;
    for (let i of numbers) {
        if (i === res) 
        	times++;
    }
    return times > Math.floor(numbers.length / 2)? res: 0;
}

最后

以上就是彪壮大白为你收集整理的剑指offer-js 数组中出现次数超过一半的数字的全部内容，希望文章能够帮你解决剑指offer-js 数组中出现次数超过一半的数字所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。