Удаление дубликатов с использованием коллекций в Java при объединении двух отсортированных массивов - PullRequest
Новая
       4

Удаление дубликатов с использованием коллекций в Java при объединении двух отсортированных массивов

1 голос
/ 23 мая 2019

Я пытаюсь изучить некоторые алгоритмы и хочу удалить дубликаты с помощью Set. Я объединяю два отсортированных массива с помощью моего маленького алгоритма, который проверяет, меньше ли число из массива A, чем B, сохраненного в C, а затем добавляет оставшиеся массивы

Я пытался, но смущается 

    //arrays must be sorted
    int a [] = {1,3,4,5};
    int b [] = {5,6,8,9,10};

    System.out.println(Arrays.toString(combineArray(a,b,3,4)));

}

private static int[] combineArray(int[] A, int[] B, int m, int n) {

    // TODO Auto-generated method stub

    int i = 0;
    int j = 0;
    int k = 0;
    int c [] = new int[9];
    while(i <= m && j <= n) {

        if(A[i] < B[j]) {

            c[k++] = A[i++];

        }else {
            c[k++] = B[j++];
        }

    }

    for(; i <=m; i++) {
        c[k++] = A[i];
    }

    for(; j <=n ; j++) {
        c[k++] = B[j];
    }




    return c;
}

Нет ошибки, просто нужна помощь по удалению дубликатов.

1 Ответ

0 голосов
/ 23 мая 2019

Вам не нужно использовать собственный алгоритм, Java 8+ может сделать это красиво и чисто: 

int[] array1 = {1, 2, 65, 4, 8, 5, 7, 18, 6, 0};
    int[] array2 = {0, 2, 11, 12, 5, 6, 8};
    int[] merged = IntStream.concat(IntStream.of(array1), IntStream.of(array2))
        .distinct()
        .sorted()
        .toArray();

Редактировать

Кажется, что вызов distinct() после sorted() быстрее.
См. Здесь:
Потоки Java: как сделать эффективный «различение и сортировка»?

Так что, вероятно, лучшеdo: 

int[] array1 = {1, 2, 65, 4, 8, 5, 7, 18, 6, 0};
    int[] array2 = {0, 2, 11, 12, 5, 6, 8};
    int[] merged = IntStream.concat(IntStream.of(array1), IntStream.of(array2))
        .sorted()
        .distinct()
        .toArray();

To your posted algorithm:

Я отладил вашу программу до следующего состояния: 

i=3, j=0 k=3.

The output of c is then: 1,3,4,0...

На этом шаге вы выполнили следующее сравнение: A[3] < B[0], то есть 5<5, чтоfalse, поэтому else входит.Там добавляется 5 из B[].На следующем шаге мы получили i=3 (nothing changed because the first if was not entered!), j=1 and k=4, поэтому мы проверяем: A[3] < B[1], что соответствует true, потому что будет добавлено 5<6, то есть A[i++], то есть A[4], что 5.Вот откуда взялась удвоенная пятерка.Теперь, как решить эту проблему?

Надеюсь, вы понимаете, что операторы if - это ваша проблема, когда вы проверяете на меньшее или равное, что фактически означает, что "разрешено" вводить условиедважды: один раз, когда первый операнд меньше второго, и второй раз, когда оба равны.Поскольку у вас есть этот случай в операторах if для обоих массивов, у вас будут дубликаты.Только одно условие if разрешено проверять на меньшее или равное.Поэтому, если вы измените свой код:

private static int [] объединить массив (int [] A, int [] B, int m, int n) {

int i = 0;
int j = 0;
int k = 0;
int c[] = new int[9];
while (i < m && j < n) {

    if (A[i] < B[j]) {

        c[k++] = A[i++];

    } else {
        c[k++] = B[j++];
    }

}


for (; i < m; i++) {
    c[k++] = A[i];
}

for (; j <= n; j++) {
    c[k++] = B[j];
}


return c;

}

Он не будет вводиться дважды и не будет добавлять дублирующиеся номера дважды.Для вашего примера, вывод:
[1, 3, 4, 5, 6, 8, 9, 10, 0]

Поскольку дубликаты удалены, есть один 0.

...