主要元素
继续算法
题目:如果数组中多一半的数都是同一个，则称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回-1。
示例 1：
输入：[1,2,5,9,5,9,5,5,5]
输出：5这题很久之前在剑指offer上看过,这次算重新复习一遍 有人把这种题目解题思路叫摩尔投票法,有人叫幸存者法,还有叫守阵地法... 我喜欢守幸存者法这个名字
思路: 首先用一个数字survivor来保存幸存者方,用一个数字count来计算幸运者幸运值 规则:如果遇到相同数字代表相同阵营,count++; 如果遇到不同数字,则幸存者count--; 如果count=0,则幸存者被取代.
注意如果存在超过一般的数字,那么这个数字肯定是幸存者,但是幸存者不一定是个数超过一般的那个.比如12213,幸存者是3,但是3个数没有超过一半.因此我们在得到幸存者后要进行验证
为什么说如果存在超过一半的数字,那么这个数字肯定是幸存者?因为如果极端的说,若其个数超过一半了,那么就算间隔着如12131514161,其他数字全由1出力干掉不用其他数字帮忙,最后也可以幸存1个
public int majorityElement(int[] nums) {
if (nums==null||nums.length==0){
return -1;
}
if (nums.length==1){
return nums[0];
}
int sur=nums[0];
int count=1;//存活计数
int index=1;//索引位置
//找出最后幸存的数
for (;index<nums.length;index++){
if (nums[index]==sur){
count++;
}else {
count--;
if (count==0){
sur=nums[index];
count=1;
}
}
}
//验证这个数是否超过一半
count=0;//个数计数,判断是否超过一半
for (index=0;index<nums.length;index++){
if (nums[index]==sur){
count++;
if (count>nums.length/2){
return sur;
}
}
}
if (count>nums.length/2){
return sur;
}else {
return -1;
}
}也有想过其他方法,比如利用hash特性,但是cpu消耗比较大
上面是hash下面是幸存者法,hash的代码在下面
public int majorityElement(int[] nums) {
Map<Integer,Integer> map=new HashMap<>();
for (Integer i: nums
) {
map.put(i,map.get(i)==null?1:map.get(i)+1);
if (map.get(i)>nums.length/2)
return i;
}
return 0;
}如果大家觉得我的方法不好,也可以去leetcode上看看别的人的方法,总能找到适合你的🤭https://leetcode-cn.com/problems/find-majority-element-lcci/comments/
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020/3/24 下，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录