Removal of Duplicate Elements: divide and conquer

Question

Removal of Duplicate Elements: divide and conquer

Navigation

#1 by (0 votes)

0

I'm having trouble getting an algorithm that removes duplicate elements in an array (it can only be integers), which uses the Divide And Conquer method. I'm needing for a college job, and unfortunately I'm 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 MergeSort logic, but instead of ordering the algorithm, whenever it found elements equal, it I cut them off from the original vector, but I got confused in the middle of the process. Here's my JAVA implementation, if anyone can show me what I did wrong, I'll 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, however it is in Python. Is it 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 algoritmo python

asked by anonymous 14.05.2018 / 22:32

1 answer

rails 5.2.0 'method_missing': undefined method 'has_one_attached' Put time (minute: second) in the graphic Flot

score 0 · Accepted Answer

Well, in the end I ended up modifying a MERGESORT algorithm, what I do is change the repeated elements to 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];
    }
}