Divide and conquer JAVA vector

Question

This is my code: import java.io.IOException; import java.util.Scanner;

public class Main {
    static int operaciones;
    public static int GetFrequency(int A[],int valor, int izq, int der){
        int cont = 0;
        for(int i=izq; i<= der; i++){
            if(A[i] == valor){
                cont++;
            }
            operaciones++;
        }
        return cont;
    }
    public static void print(int A[]){
        System.out.println("El vector Ingresado Fue: ");
        System.out.println("--------------------------");
        for(int i=1; i<A.length;i++){
            System.out.print(A[i] + "\n");
        }
    }
    public static void ingresar(int A[], int elementos, Scanner sc){
        System.out.println("Ingrese los elementos");
        for(int i=1; i<A.length;i++){
            elementos = sc.nextInt();
            A[i]=elementos;
        }
    }
    public static boolean mayoritario(int A[],int i, int j){
        if(i<=j){
            int valor = 0;
            for(int x = i; i <j; x++){
            valor = GetFrequency(A, A[x], i, j);
            operaciones++;
            }
            if(((A.length-1)%2) == 0){
                if(valor > (A.length-1)/2){
                    return true;
                }
            }else{
                if(valor >= (A.length/2)){
                    return true;
                }
            }
            return false;
        }
        if(mayoritario(A,i,j/2)){
            return true;
        }if(mayoritario(A,((i+(j/2))),j)){

            return true;
        }
        return false;

    }
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        System.out.println("Ingrese cantidad de elementos");
        int n = sc.nextInt();
        int A [] = new int [n+1];
        int elementos = 0;
        int maximo = n;
        int minimo = 1;
        ingresar(A,elementos,sc);
        print(A);
        System.out.println("-------------------------");
        if(mayoritario(A,minimo,maximo)){
            System.out.println("Existe un mayoritario");
        }else{
            System.out.println("No existe un mayoritario");
        }
        System.out.println("Operaciones = "+operaciones);

    }

}

I need to find the most repeated num with getfrequency and divide and conquer, but I have a T(n) = n^2, and this supposed to be T(n) = nlog(n). I think I need to merge my solutions but I dont know how to do this. any suggestion ?

Answer 1

Instead of running GetFrequency at every iteration, break your problem into two steps. In step 1, tabulate your frequencies into a Map. You should be able to do this in O(n). In step 2, iterate through the Map and find the key associated with the largest value.