分而治之JAVA向量

Question

这是我的代码： 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); 

    } 

} 

我需要找到与getfrequency和分而治之最重复次数，但是我有T（N）= N^2，这应该是T（N）= n日志（N）。 我想我需要合并我的解决方案，但我不知道如何做到这一点。任何建议？

Answer 1

而不是在每次迭代运行GetFrequency，将问题分为两步。在第1步中，将您的频率列入地图。你应该可以在O（n）中做到这一点。在第2步中，遍历Map并找到与最大值关联的键。