众数问题(Java语言)

方法1：分治法

import java.util.Scanner;

public class Mode2 {
    public static int n1 ; //众数
    public static int n2 ; //重数
    public static int count(int [] arr, int left, int right){ //找到等于中间值元素的元素个数
        int sum = 0 ;
        int mid = (left + right) >>> 1 ;
        int n = arr[mid] ;
        for(int i=left; i<right; i++){
            if(arr[i] == n){
                sum ++ ;
            }
        }
        return sum ;
    }
    public static int start(int [] arr, int left, int right){ //找出等于中间值元素的第一个元素下标
        int x = 0 ;
        int mid = (left + right) >>> 1 ;
        for(int i=left; i<right; i++){
            if(arr[mid] == arr[i]){
                x = i ;
            }
        }
        return x ;
    }
    public static void mode(int [] arr, int first, int last){
        int sum = count(arr, first, last) ; //找出有多少个与中间值相等的
        int left = start(arr, first, last) ; //找出第一个与中间值相等的元素下标
        if(sum > n2){ //更新众数和重数
            n1 = arr[left] ;
            n2 = sum ;
        }
        if(left > n2){ //如果左边的元素个数大于重数，向左搜索
            mode(arr, first, left) ;
        }
        if((last-left-sum) > n2){ //如果右边的元素个数大于重数，向右搜索
            mode(arr, left+sum, last) ;
        }
    }
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in) ;
        int n = input.nextInt() ;
        int [] arr = new int [n] ;
        for(int i=0; i<arr.length; i++){
            arr[i] = input.nextInt() ;
        }
        mode(arr, 0, n) ;
        System.out.println(n1);
        System.out.println(n2);
    }
}

方法2：顺序查找法

import java.util.Scanner;

public class Mode1 {
    public static void find(int [] arr, int n){
        int max = Integer.MIN_VALUE ;
        int count = 1;
        int res = Integer.MIN_VALUE ;
        for(int i=0; i<n-1; i++){
            if(arr[i+1] != arr[i]){
                count = 1 ;
            }
            if(arr[i+1] == arr[i]) {
                count++;
                if(count > max){
                    max = count ;
                    res = arr[i] ;
                }
            }
        }
        System.out.println(res);
        System.out.println(max);
    }
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in) ;
        int n = input.nextInt() ;
        int [] arr = new int [n] ;
        for(int i=0; i<arr.length; i++){
            arr[i] = input.nextInt() ;
        }
        find(arr, n) ;
    }
}