logo标签列表

在Java中合并两个数组并去除重复项

javaarraysmergeduplicates
3

我在将两个数组合并成一个后，无法删除其中的重复项。我已经编写了以下代码来合并这些数组，但是我不知道如何从最终的数组中删除重复项。假设这些数组已经排序。

public static int[] merge(int[] list1, int[] list2) {
    int[] result = new int[list1.length + list2.length];

    int i = 0;
    int j = 0;

    for (int k = 0; k < (list1.length + list2.length); k++) {
        if (i >= list1.length) {
            result[k] = list2[j];
            j++;
        } 
        else if (j >= list2.length) {
            result[k] = list1[i];
            i++;
        } 
        else {
            if (list1[i] < list2[j]) {
                result[k] = list1[i];
                i++;
            } else {
                result[k] = list2[j];
                j++;
            }
        }
    }
    return result;
}
在合并前将它们移除。 - user5156016
我不知道问题的背景是什么，或者你的程序内存使用/速度有多关键，但你应该开始使用集合。你可以用一两行代码完成所有这些操作。 - MikaelF
集合将把所有内容包装成整数，如果你使用的是HashSet，它会创建大量的内部对象。如果你的数组大小相当大，或者你经常使用这个功能，你应该使用标准算法来完成这个操作，我在下面给出了示例。 - rghome
请注意，这是一个相当旧的问题。在内存消耗上的权衡（对于以百万计大小的集合而言，在一个Set<Integer>中可能是以MB为单位，而不是以GB为单位）是，您可以节省CPU消耗的成本（O(1)的检查与O(n)的检查相比）。对于这个问题来说，HashSet是行不通的，因为它是无序的，而且OP拥有排序数据。 - Rogue
@Rouge 不仅仅是内存空间的问题，而是分配内存的开销；也就是说，所有这些整数和其他对象（取决于你使用的类）以及它们必须进行垃圾回收。这并不涉及时空权衡。使用集合会更慢且占用更多内存。权衡的是是否值得程序员花时间找到最佳解决方案（因此这个网站的实用性就体现出来了！）。 - rghome
8个回答
5

好的，有人不喜欢之前的答案。这里有另一个尝试，结合了两个stackoverflow问题：合并数组和去重。

这个方法在处理两个包含一百万个整数的列表时运行速度比我之前的尝试要快得多。

public int[] mergeArrays2(int[] arr1, int[] arr2){
    int[] merged = new int[arr1.length + arr2.length];
    System.arraycopy(arr1, 0, merged, 0, arr1.length);
    System.arraycopy(arr2, 0, merged, arr1.length, arr2.length);

    Set<Integer> nodupes = new HashSet<Integer>();

    for(int i=0;i<merged.length;i++){
        nodupes.add(merged[i]);
    }

    int[] nodupesarray = new int[nodupes.size()];
    int i = 0;
    Iterator<Integer> it = nodupes.iterator();
    while(it.hasNext()){
        nodupesarray[i] = it.next();
        i++;
    }



    return nodupesarray;
}

控制台输出:

INFO [main] (TestMergeArray.java:40) - creating two lists of a million ints
DEBUG [main] (TestMergeArray.java:41) - list 1 size : 1000000
DEBUG [main] (TestMergeArray.java:42) - list 2 size : 1000000
INFO [main] (TestMergeArray.java:56) - now merging
INFO [main] (TestMergeArray.java:59) - done, final list size is 864975
1
这个回答没有考虑到用户正在合并两个已排序的数组，并且想要保持排序。 - Patrick Parker
3

这个更清晰的lambda解决方案稍微慢一些，因为需要（取消）装箱。
需要Java 8或以上版本。

public static int[] mergedistinct( int[] array1, int[] array2 ) {
  Stream<Integer> s1 = IntStream.of( array1 ).boxed();
  Stream<Integer> s2 = IntStream.of( array2 ).boxed();
  return( Stream.concat( s1, s2 ).distinct().mapToInt( i -> i ).toArray() );
}

[1, 2, 3, 4, 5, 7, 8]

如果您需要对数组进行排序：

…
return( Stream.concat( s1, s2 ).distinct().sorted().mapToInt( i -> i ).toArray() );
还有一个IntStream.concat()方法，可以这样使用：int[] foo = IntStream.concat(intStream1, intStream2).distinct().toArray();，也许这样可以避免装箱和拆箱的问题？ - Weekend
1
这是一种只迭代一次数组且不使用哈希来检测重复项的技术。
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

public class SortedMerge {
    public static int[] merge(int[] array1, int[] array2) {
        int[] a;
        int[] b;
        List<Integer> c = new ArrayList<Integer>();
        int i = 0;
        int j = 0;

        // b is longer than a
        if (array1.length > array2.length) {
            a = array2;
            b = array1;
        } else {
            a = array1;
            b = array2;
        }

        while (j < b.length) {
            int bb = b[j];

            if (i < a.length) {
                int aa = a[i];

                if (aa > bb) {
                    c.add(bb);
                    j++;
                } else {
                    c.add(aa);
                    i++;
                    if (aa == bb) {
                        j++;
                    }
                }
            } else {
                c.add(bb);
                j++;
            }
        }
        // java 8 List<Integer> to int[]
        return c.stream().mapToInt(Integer::intValue).toArray();
    }

    public static void main(String[] args) throws Exception {
        int[] array1 = new int[]{3, 5, 8, 11, 14};
        int[] array2 = new int[]{1, 2, 3, 4, 6, 8, 14, 15, 17};
        int[] c = merge(array1, array2);

        for (int i = 0; i < c.length; i++) {
            System.out.format("%d,", c[i]);
        }
        System.out.println();
        // output> 1,2,3,4,5,6,8,11,14,15,17,
    }
}
0
调用您的merge方法并执行以下操作。我已经测试过了，它可以正常工作。
int[] result = merge(count, count1);

Set<Integer> set = new HashSet<Integer>();
try {
    for (int i = 0; i < result.length; i++) {
        set.add(result[i]);
    }
    System.out.println(set);
} catch (Exception e) { }
0
import java.util.ArrayList;
import java.util.List;
public class MergeListAndRemoveDuplicate {
    public static void main(String[] args) {
        int a[] = {1, 1, 2, 1, 3, 4, 1, 2, 5};
        int b[] = {1, 2, 3, 1, 3, 2, 4, 5, 6, 7};

        boolean flag = true;
        List<Integer> list = new ArrayList<Integer>();

        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < b.length; j++) {
                if (a[i] == b[j]) {
                    flag = false;
                }
                if (i == j && !list.contains(b[j])) {
                    list.add(b[j]);
                }
            }
            if (flag == true) {
                list.add(a[i]);
            }
        }
        System.out.println(list);
    }
}
0
package com.string.merge;

import java.util.ArrayList;

public class MergeArrayAndRemoveDuplicate {
    public static void main(String[] args) {
        int[] a = {1, 2, 2, 3, 1, 5, 3};
        int[] b = {4, 3, 1, 5, 7, 8, 4, 2};

        ArrayList<Integer> l = new ArrayList<>();
        for (int i = 0; i < (a.length > b.length ? a.length : b.length); i++) {
            if (i < a.length) {
                int c = 0;
                while (c <= l.size()) {
                    if (l.contains(a[i]) == false) {
                        l.add(a[i]);
                    }
                    c++;
                }
            }
            if (i < b.length) {
                int c = 0;
                while (c <= l.size()) {
                    if (l.contains(b[i]) == false) {
                        l.add(b[i]);
                    }
                    c++;
                }
            }
        }
        System.out.println(l);
    }
}


o/p-[1, 4, 2, 3, 5, 7, 8]
0

你能使用ArrayList吗？使用ArrayList会让这个任务变得非常容易。

 //Consider n1 to be some global or instance variable.

 import java.util.ArrayList;
 public void Add(ArrayList<Integer> n2) {

     for(int i = 0; i < n2.size(); i++) {
         if(!n1.contains(i))
             n1.add(n2.get(i));
     }
}
0
有一个已知的算法可以解决这个问题。你不应该使用集合或列表，因为它们会消耗内存并且运行缓慢，而没有任何好处。
下面是一个简单、标准且相当优化的解决方案，用于合并已排序的数组。它假设输入的数组已经排序，并且包含唯一的整数。
public static int[] mergeSortedArrays(int[] array1, int[] array2) {
    int[] result = new int[array1.length + array2.length];
    int i = 0, j = 0, k = 0;
    while (i < array1.length) {
        while (j < array2.length && array2[j] < array1[i]) {
            result[k++] = array2[j++];
        }
        if (j < array2.length && array2[j] == array1[i]) {
            j++;
        }
        result[k++] = array1[i++];
    }
    while (j < array2.length) {
        result[k++] = array2[j++];
    }

    if (k != result.length) {
        result = Arrays.copyOf(result, k);
    }
    return result;
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接