时间戳

首页 > 解决方案 > 合并两个排序数组时使用Java中的集合删除重复项

java - 合并两个排序数组时使用Java中的集合删除重复项

问题描述

我正在尝试学习一些算法，我想使用 Set 删除重复项。我正在使用我的小算法合并两个排序数组，该算法检查数组 A 中的数字是否小于 C 中存储的 B，然后添加剩余的数组

我已经尝试过，但一直感到困惑

    //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;
}

没有错误只是需要一些帮助来删除重复项。

标签： javaduplicates

解决方案

你不需要使用自己的算法，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()aftersorted()更快。
请参阅此处：
Java Streams：如何进行有效的“区分和排序”？

所以最好这样做： 

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<5which is false，因此else进入。在那里，添加了5of B[]。在下一步中，我们得到了i=3 (nothing changed because the first if was not entered!), j=1 and k=4，因此我们正在检查：A[3] < B[1]which 的计算结果为true，因为5<6, soA[i++]将被添加，即A[4]which is 5。这就是加倍五的来源。现在如何解决这个问题？

我希望您清楚 if 语句是您检查较小或等于的问题，这实际上意味着“允许”两次输入条件：一次是第一个操作数小于第二次和第二次都相等时。由于您在两个数组的 if 语句中都有这种情况，因此您将有重复项。只允许一个 if 条件来检查是否小于或等于。因此，如果您更改代码：

私有静态 int[] combineArray(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.

推荐阅读