分而治之 JAVA 矢量

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 和分治法找到重复次数最多的 num，但我有一个 T(n) = n^2，这应该是 T(n) = nlog(n)。我想我需要合并我的解决方案，但我不知道该怎么做。有什么建议吗？

Answer 1

而不是在每次迭代时运行 GetFrequency，将您的问题分成两步。在第 1 步中，将您的频率制成地图。您应该能够在 O(n) 中执行此操作。在第2步中，遍历Map并找到与最大值关联的键。

分而治之 JAVA 矢量

Divide and conquer JAVA vector

java

algorithm

divide-and-conquer

divide