繼續(xù)算法
題目:如果數(shù)組中多一半的數(shù)都是同一個(gè)，則稱之為主要元素凡蚜。給定一個(gè)整數(shù)數(shù)組，找到它的主要元素吭从。若沒(méi)有朝蜘，返回-1。
示例 1：
輸入：[1,2,5,9,5,9,5,5,5]
輸出：5
這題很久之前在劍指offer上看過(guò),這次算重新復(fù)習(xí)一遍
有人把這種題目解題思路叫摩爾投票法,有人叫幸存者法,還有叫守陣地法...
我喜歡守幸存者法這個(gè)名字
思路:
首先用一個(gè)數(shù)字survivor來(lái)保存幸存者方,用一個(gè)數(shù)字count來(lái)計(jì)算幸運(yùn)者幸運(yùn)值
規(guī)則:如果遇到相同數(shù)字代表相同陣營(yíng),count++;
如果遇到不同數(shù)字,則幸存者count--;
如果count=0,則幸存者被取代.
注意如果存在超過(guò)一般的數(shù)字,那么這個(gè)數(shù)字肯定是幸存者,但是幸存者不一定是個(gè)數(shù)超過(guò)一般的那個(gè).比如12213,幸存者是3,但是3個(gè)數(shù)沒(méi)有超過(guò)一半.因此我們?cè)诘玫叫掖嬲吆笠M(jìn)行驗(yàn)證
為什么說(shuō)如果存在超過(guò)一半的數(shù)字,那么這個(gè)數(shù)字肯定是幸存者?因?yàn)槿绻麡O端的說(shuō),若其個(gè)數(shù)超過(guò)一半了,那么就算間隔著如12131514161,其他數(shù)字全由1出力干掉不用其他數(shù)字幫忙,最后也可以幸存1個(gè)
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;//存活計(jì)數(shù)
int index=1;//索引位置
//找出最后幸存的數(shù)
for (;index<nums.length;index++){
if (nums[index]==sur){
count++;
}else {
count--;
if (count==0){
sur=nums[index];
count=1;
}
}
}
//驗(yàn)證這個(gè)數(shù)是否超過(guò)一半
count=0;//個(gè)數(shù)計(jì)數(shù),判斷是否超過(guò)一半
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下面是幸存者法,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;
}
如果大家覺(jué)得我的方法不好,也可以去leetcode上看看別的人的方法,總能找到適合你的??https://leetcode-cn.com/problems/find-majority-element-lcci/comments/
