Removal of Duplicate Elements : divide and Conquer

Asked

Viewed 98 times

0

I’m having trouble getting an algorithm that removes duplicate elements in an array (can only be integers), which uses the method Divide And Conquer. I am in need for a college job, and unfortunately I am not able to find/implement an algorithm in Java.

EDIT : I tried to create an algorithm without success, my initial idea was to do something that used the logic of Mergesorte, but instead of ordering the algorithm, whenever it found equal elements, it cut them from the original vector, but I got confused in the middle of the process. There is my implementation in JAVA, if anyone can show me what I did wrong, I will be grateful.

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: I found a possible solution to my problem, but it is in Python. It would be possible to convert it to 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]))
java python algorithm
  • 3

    Got nothing? Not even starting the program? So, considering it’s a college job, it seems to me you’ll need to revise the basics. Start by searching how you define yourself and work with a array and research what the technique is divides and Conquer. After that you will demonstrably be able, if you don’t do the exercise, to do a good part of it.

  • I managed to make an algorithm, but it became unviable for big numbers, so I’m definitely on the other side

  • Then add to the question this algorithm, explain how you did it and what your problem is. With that we can reopen the question and help you.

  • Right, I followed an example of stack overflow even trying to modify the merge function of Mergesort.

  • With a little experimentation I got a modification in the MERGE algorithm of merge and Sort, this solved my problem.

1 answer

0


Well, in the end I managed to modify an algorithm of MERGESORT, what I do is to exchange the repeated elements for 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];
    }
}

Browser other questions tagged java python algorithm

You are not signed in. Login or sign up in order to post.