0

Estou tendo problemas em conseguir um algoritmo que remova elementos duplicados em um array (pode ser somente inteiros), que use o método Divide And Conquer. Estou precisando para um trabalho de faculdade, e infelizmente não estou conseguindo encontrar/implementar um algoritmo em Java.

EDIT : Eu tentei criar um algoritmo sem sucesso, a minha ideia inicial era fazer algo que usasse a lógica do MergeSorte, porém ao invés de ordenar o algoritmo, sempre que ele achasse elementos iguais, ele os cortasse do vetor original, mas eu me confundi no meio do processo. Ai está a minha implementação em JAVA, se alguém puder me mostrar o que fiz errado, serei grato.

public static int[] merge(int[] leftArray, int[] rightArray) {
int leftArrayEnd = leftArray.length - 1;
int rightArrayEnd = rightArray.length - 1;
int leftArrayBegin = 0;
int rightArrayBegin = 0;

int numElements = leftArray.length + rightArray.length;
int[] resultArray = new int[numElements];
int resultArrayBegin = 0;

while (leftArrayBegin <= leftArrayEnd && rightArrayBegin <= rightArrayEnd) {
  if (leftArray[leftArrayBegin] <= rightArray[rightArrayBegin]) {
    resultArray[resultArrayBegin++] = leftArray[leftArrayBegin++];
  } else if (leftArray[leftArrayBegin] > rightArray[rightArrayBegin]) {
    resultArray[resultArrayBegin++] = rightArray[rightArrayBegin++];
  } else {
    //ITEMS IGUAIS
    //INCREMENTA NA DIREITA
    rightArrayBegin++;
  }
}

while (leftArrayBegin <= leftArrayEnd) {
  resultArray[resultArrayBegin++] = leftArray[leftArrayBegin++];
}

while (rightArrayBegin <= rightArrayEnd) {
  resultArray[resultArrayBegin++] = rightArray[rightArrayBegin++];
}

return resultArray;

EDIT2: Eu achei uma possível solução para o meu problema, porém ela está em Python. Seria possível converte-la para Java?

def merge(left, right):
result = []
while left and right:
    small, big = min(left, right), max(left, right)
    result.append(small[0])
    left, right = ((left[1:], right[1:])
                   if small[0] == big[0]
                   else (small[1:], big))

def remove_duplicates(candidates):
if not candidates or len(candidates) == 1:
    return candidates
return merge(remove_duplicates(candidates[1::2]),
             remove_duplicates(candidates[::2]))
5
  • 3
    Não conseguiu nada? Nem começar o programa? Então, considerando que é um trabalho de faculdade, parece-me que você precisará revisar o básico. Comece pesquisando como se define e trabalha com um array e pesquise o que é a técnica divide and conquer. Depois disso você comprovantemente conseguirá, se não fazer o exercício, fazer boa parte dele.
    – Woss
    Commented 14/05/2018 às 23:22
  • Eu consegui fazer um algoritmo, mas ele ficou inviável para números grandes, então eu com certeza estou na contra mão Commented 17/05/2018 às 13:05
  • Então adicione à pergunta esse algoritmo, explique como o fez e qual é o problema dele. Com isso conseguiremos reabrir a pergunta e te ajudar.
    – Woss
    Commented 17/05/2018 às 13:08
  • Certo, eu segui um exemplo do stack overflow mesmo de tentar modificar a função merge do MergeSort. Commented 17/05/2018 às 16:36
  • Com um pouco de experimentação eu consegui uma modificação no algoritmo MERGE do merge and sort, isso resolveu meu problema. Commented 18/05/2018 às 17:50

1 Resposta 1

0

Bom, no final eu acabei conseguindo modificar um algoritmo de MERGESORT, o que eu faço é trocar os elementos repetidos por 0.

static void merge(int[] A, int p, int q, int r) {
    int[] aux = new int[r - p + 1];
    int a = p;
    int b = q + 1;
    int h = 0;
    while (a <= q && b <= r) {
        if (A[a] < A[b]) {
            aux[h++] = A[a++];
        } else if (A[a] > A[b]) {
            aux[h++] = A[b++];
        } else {
            b++;
        }
    }
    while (a <= q) {
        aux[h++] = A[a++];
    }
    while (b <= r) {
        aux[h++] = A[b++];
    }
    for (h = 0; h < aux.length; h++) {
        A[p++] = aux[h];
    }
}

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .