-
首先想到哈希表解法HashMap<元素,元素出现个数>,
遍历数组时记录元素个数,超过数组一半返回该元素 - 然后看题解,使用排序法+数组特性,直接找中位数
- 最后看了大佬的 "阵地战"解法,很有意思(最差情况就是元素A与全部其他元素抵消,最后还是剩下数量超过一半的A | 其他情况其它杂元素B,C也可能会相互抵消,不过反正剩下的总是A)
import java.util.*; public class Solution { /*数组中出现次数超过一半的数字 1.哈希表 -需要计算数组中元素出现的个数:使用hashMap -每次遍历遇到重复元素时判断value是否超过数组长度一半 2.数组特性:某元素个数超过数组的一半,则必定存在相邻重复元素,必定在排序后中位数是该重复元素 - a.排序后,直接取中位数 - b.解法3 3.士兵阵地战(留到最后的就是元素最多的那个 元素最多的A,对其他杂元素B) - 遍历数组,元素res 与上个士兵一致count++,否则count-- - 若count==0,阵地被敌方占领,重置 res与count - 遍历完数组可以得到 士兵最多的那个元素 - 最后判断该元素数量是否超过数组一半 */ public int MoreThanHalfNum_Solution(int [] array) { //阵地战 int res = array[0]; int count = 1; for(int i=1;i<array.length;i++){ if(res==array[i]){ count++;//友军 }else{ count--; if(count==0){ //阵地被占领,换新的一方 res=array[i]; count=1; } } } //攻守结束,res即为最后剩下的count最多的一方 //验证一下结果 return res; } }