《剑指offer》数组中出现次数超过数组长度一半的数字
《剑指offer》数组中出现次数超过数组长度一半的数字
ConardLi
发布于 2019-05-23 22:34:40
发布于 2019-05-23 22:34:40
本系列是《剑指offer》或leetcode的JavaScript版本。 每期1-2个算法，也有可能是一个类别。 文章包括题目、思路以及代码。 如果您对本期有不同或者更好的见解，请后台留言，喜欢请点个好看，谢谢阅读。
题目
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
代码
解法1: 开辟一个额外空间存储每个值出现的次数，时间复杂度最大为O(n)，逻辑简单
function MoreThanHalfNum_Solution(numbers) {
if (numbers && numbers.length > 0) {
var length = numbers.length;
var temp = {};
for (var i = 0; i < length; i++) {
if (temp['s' + numbers[i]]) {
temp['s' + numbers[i]]++;
} else {
temp['s' + numbers[i]] = 1;
}
if (temp['s' + numbers[i]] > length / 2) {
return numbers[i];
}
}
return 0;
}
}解法2:
目标值的个数比其他所有值加起来的数多
记录两个变量 1.数组中的某个值 2.次数
1.当前遍历值和上一次遍历值相等？次数+1 ： 次数-1。
2.次数变为0后保存新的值。
3.遍历结束后保存的值,判断其是否复合条件 事件复杂度O(n) 不需要开辟额外空间 , 逻辑稍微复杂。
function MoreThanHalfNum_Solution(numbers) {
if (numbers && numbers.length > 0) {
var target = numbers[0];
var count = 1;
for (var i = 1; i < numbers.length; i++) {
if (numbers[i] === target) {
count++;
} else {
count--;
}
if (count === 0) {
target = numbers[i];
count = 1;
}
}
count = 0;
for (var i = 0; i < numbers.length; i++) {
if (numbers[i] === target) count++;
}
return count > numbers.length / 2 ? target : 0;
}
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-03-07，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录