【剑指Offer】39. 数组中出现次数超过一半的数字

NowCoder

解题思路
Hash法

import java.lang.Integer;
import java.util.HashMap;

import java.util.*;
import java.lang.*;

public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if(array.length == 0)
return 0;

HashMap map = new HashMap<>();
for(int sum: array) {
map.put(sum,map.containsKey(sum) ? (int)map.get(sum)+1 : 1);
if((int)map.get(sum) > (array.length / 2))
return sum;
}

return 0;
}
}

众数法


import java.util.*;
import java.lang.*;

public class Solution {
public int MoreThanHalfNum_Solution(int[] nums) {
Arrays.sort(nums);
// 众数一定在符合条件的中间
int val = nums[nums.length / 2];
int count = 0;
for(int i : nums) {
if(i == val)
count++;
}
if(count > nums.length / 2) return val;
return 0;
}
}


多数投票法

多数投票问题,可以利用 Boyer-Moore Majority Vote Algorithm 来解决这个问题,使得时间复杂度为 O(N)。

使用 cnt 来统计一个元素出现的次数,当遍历到的元素和统计元素相等时,令 cnt++,否则令 cnt–。如果前面查找了 i 个元素,且 cnt == 0,说明前 i 个元素没有 majority,或者有 majority,但是出现的次数少于 i / 2 ,因为如果多于 i / 2 的话 cnt 就一定不会为 0 。此时剩下的 n - i 个元素中,majority 的数目依然多于 (n - i) / 2,因此继续查找就能找出 majority。

加入数组中存在众数,那么众数一定大于数组的长度的一半。
思想就是:如果两个数不相等,就消去这两个数,最坏情况下,每次消去一个众数和一个非众数,那么如果存在众数,最后留下的数肯定是众数。

具体做法:

初始化:候选人cond = -1, 候选人的投票次数cnt = 0
遍历数组,如果cnt=0, 表示没有候选人,则选取当前数为候选人,++cnt
否则,如果cnt > 0, 表示有候选人,如果当前数=cond,则++cnt,否则–cnt
直到数组遍历完毕,最后检查cond是否为众数

import java.lang.Integer;
import java.util.HashMap;

import java.util.*;
import java.lang.*;

public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if(array.length == 0)
return 0;

int val = -1, count = 0;
for(int sum : array) {
if(count == 0) {
val = sum;
count++;
}else {
if(val == sum) count++;
else count--;
}
}
count = 0;
for(int sum : array) {
if(val == sum) count++;
}

if(count > array.length / 2) return val;
return 0;
}
}

【剑指Offer】39. 数组中出现次数超过一半的数字

瑞 新

【剑指Offer】39. 数组中出现次数超过一半的数字
CSDN认证博客专家


分布式
Java
架构

求职中 • Java全栈养成计划
公众号 • 让我遇见相似的灵魂
回复领取:竞赛 书籍 项目 面试

左手代码,右手吉他,这就是天下:如果有一天我遇见相似的灵魂 那它肯定是步履艰难 不被理解 喜黑怕光的。如果可以的话 让我触摸一下吧 它也一样孤独得太久。 不一样的文艺青年,不一样的程序猿。

关注博主即可阅读全文


原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

【剑指Offer】39. 数组中出现次数超过一半的数字

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 【剑指Offer】39. 数组中出现次数超过一半的数字
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏