剑指offer - 数组中出现次数超过一半的数字 - JavaScript
剑指offer - 数组中出现次数超过一半的数字 - JavaScript
心谭博客
发布于 2020-04-21 10:43:25
发布于 2020-04-21 10:43:25
题目描述：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
题目分析
题目假设很重要，数组非空，且一定存在存在多数的元素。
解法 1: 哈希表统计次数
借助哈希表，哈希表的键是数字，值是数字出现的次数。整体流程如下：
- 遍历数组，统计数字和出现次数
- 遍历哈希表，返回出现次数超过长度一半的数字
注意，这里要使用 ES6 的 Map，不要使用 json 对象。因为 json 对象的键存在着“隐式类型转换”，所有的键会被转换为字符串，从而导致不易排查的 bug。代码实现如下：
// ac地址：https://leetcode-cn.com/problems/majority-element/
// 原文地址：https://xxoo521.com/2020-02-07-half-number/
/**
* @param {number[]} nums
* @return {number}
*/
var majorityElement = function(nums) {
const map = new Map();
const length = nums.length;
nums.forEach(num => {
const times = map.get(num);
if (times === undefined) {
map.set(num, 1);
} else {
map.set(num, times + 1);
}
});
for (const key of map.keys()) {
if (map.get(key) > length / 2) {
return key;
}
}
return 0;
};遍历两次，时间复杂度是 O(N)。哈希表存储次数，空间复杂度是 O(N)。
解法 2（推荐）：摩尔投票算法
题目说了：只可能有 1 个数字的出现次数超过数组长度的一半。也就是说这个数字的出现总数比其他数字的出现次数和还要多。
定义变量 result 和 times。第一次遍历原数组的时候：
- times = 0，那么 result 等于当前元素，times 变为 1
- times != 0 且 result != 当前元素，times 减 1
- times != 0 且 result = 当前元素，times 加 1
遍历完成后，result 的值就是数组中出现次数超过一半的数字了。
// ac地址：https://leetcode-cn.com/problems/majority-element/
// 原文地址：https://xxoo521.com/2020-02-07-half-number/
/**
* @param {number[]} nums
* @return {number}
*/
var majorityElement = function(nums) {
let times = 0;
let result = 0;
nums.forEach(number => {
if (times === 0) {
times = 1;
result = number;
} else if (number === result) {
times += 1;
} else {
// number !== result
times -= 1;
}
});
return result;
};时间复杂度 O（N）。空间复杂度是 O（1）。比解法 1 更优。
感谢@ℭ?????的提醒，题目已经假设了一定存在多数的元素，不需要二次遍历进行确定。
拓展思考
如果题目没假设数组中一定存在数目大于一半的元素，例如[1, 2, 3]。此时还需要遍历一遍，统计一下 result 的出现次数。
// ac地址：https://leetcode-cn.com/problems/majority-element/
// 原文地址：https://xxoo521.com/2020-02-07-half-number/
/**
* @param {number[]} nums
* @return {number}
*/
var majorityElement = function(nums) {
let times = 0;
let result = 0;
nums.forEach(number => {
if (times === 0) {
times = 1;
result = number;
} else if (number === result) {
times += 1;
} else {
times -= 1;
}
});
// 第二次遍历，统计result的次数
times = 0;
nums.forEach(number => number === result && times++);
return times > nums.length / 2 ? result : 0;
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-02-07，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录