hash
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param numbers int整型一维数组 * @return int整型 */ public int MoreThanHalfNum_Solution (int[] numbers) { // write code here Map<Integer,Integer> hashMap=new HashMap<>(); int len=numbers.length; for(int i=0;i<len;i++){ hashMap.put(numbers[i],hashMap.getOrDefault(numbers[i],0)+1); if(hashMap.getOrDefault(numbers[i],0)>len/2){ return numbers[i]; } } return 0; } }
候选法
加入数组中存在众数,那么众数一定大于数组的长度的一半。
思想就是:如果两个数不相等,就消去这两个数,最坏情况下,每次消去一个众数和一个非众数,那么如果存在众数,最后留下的数肯定是众数。
参考:https://blog.nowcoder.net/n/34901ad298694eacaa1a32da61a018be
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param numbers int整型一维数组 * @return int整型 */ public int MoreThanHalfNum_Solution (int[] numbers) { // write code here int len=numbers.length; int cond=-1; int count=0; for(int i=0;i<len;i++){ if(count==0){ cond=numbers[i]; count++; }else{ if(cond==numbers[i]){ count++; }else{ count--; } } } return cond; } }