나누고 정복 자바 벡터

Question

이것은 내 코드입니다 가져 오기 java.io.IOException; 가져 오기 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) = nlog (n)이 있어야하는데. 내 솔루션을 병합해야한다고 생각하지만이를 수행하는 방법을 모른다. 어떠한 제안 ?

Answer 1

반복 할 때마다 GetFrequency을 실행하는 대신 두 단계로 문제를 해결하십시오. 1 단계에서 귀하의 빈도를지도로 집계하십시오. O (n)에서이 작업을 수행 할 수 있어야합니다. 2 단계에서 Map을 반복하고 가장 큰 값과 연결된 키를 찾습니다.