(三种方法)数组中出现次数超过一半的数字

数组中出现次数超过一半的数字

方法1 HashMap

思想 :

利用HashMap计算每一次数组元素出现的次数,然后在判断这个数是不是众数(看有没有超过数组元素的一半)

代码实现:

import java.util.*;
public class Solution {
    public int MoreThanHalfNum_Solution (int[] numbers) {
        Scanner scanner = new Scanner(System.in);
        HashMap<Integer,Integer> map = new HashMap<>();
        int len = numbers.length;   
        for(int x : numbers) {
           map.put(x,map.getOrDefault(x,0)+1);
        }
        int max = 0;
         for(int x : numbers) {
                if(map.get(x) > len/2) {
                    max = x;
                }
         }
       return max; 
    }
    
}

方法2 排序

思想:

将数组进行排序,如果存在众数,说明中间的数就是众数 不存在返回0;

代码实现

public class Solution {
    public int MoreThanHalfNum_Solution (int[] numbers) {
        if(numbers == null || numbers.length == 0) {
            return 0;
        }
        Arrays.sort(numbers);
        int len = numbers.length;
        int midNum = numbers[len/2];
        int time = 0;
        for(int i = 0; i < len; i++) {
            if(numbers[i] == midNum) {
                time++;
            }
        }
        if(time > len/2) {
            return midNum;
        }
        return 0;
    }
}

方法3 消除(加分思路)

思想:

利用众数 和 非众数相互抵消 ,如果两个数不相等,就消除这两个数

如果众数存在,最后留下的数一定是众数

代码实现

import java.util.*;


public class Solution {
    public int MoreThanHalfNum_Solution (int[] numbers) {
        if(numbers == null || numbers.length == 0) {
            return 0;
        }
        int len = numbers.length;
        int res = numbers[0];
        int time = 1;
        //记录下标0的值,以及出现的次数1;
        //如果如果后面出值相同则次数加一,不同减一
        for(int i = 1; i < len; i++) {
            if(time != 0) {
                if(numbers[i] == res) {
                    time++;
                } else {
                    time--;
                }
              //time == 0 说明这个数出现次数被抵消完了,
              //将当前的下标元素赋值给res,次数重新计算
            } else {
                res = numbers[i];
                time = 1;
            }
        }
        int count = 0;
        for(int i = 0; i < len; i++) {
            if(numbers[i] == res) {
                count++;
            }
        }
       // 判断是不是众数
        if(count > len/2) {
            return res;
        }
        return 0;
    }
}