java - 在Java中不使用Set合并两个未排序的整数数组

Question

给定两个整数数组，创建第三个数组，其中包含两个数组中的非重复值。无法在 Java 中使用 Set 实现，这是我解决它的方法，我希望找到一个具有更好运行时复杂性的解决方案。

我的实现:

public static void removeDuplicates(int[] arr1, int[] arr2){
        int[] arr = new int[arr1.length + arr2.length];
        int index=0,i,j;

        for (i=0;i<arr1.length;i++){
            if(!contains(arr, arr1[i])){
                arr[index++]=arr1[i];
            }
        }

        for (j = 0; j < arr2.length; j++) {
            if (!contains(arr, arr2[j])) {
                arr[index++] = arr2[j];
            }
        }

        for (int a: arr)
            System.out.println(a);
    }

    private static boolean contains(int[] arr, int i) {
        for (int a: arr){
            if(a==i) return true;
        }
        return false;
    }

Answer 1

由于contains，这确实具有二次复杂度。来电。您可以通过首先对两个数组进行排序来改进算法，然后进行类似于合并排序的合并步骤中所做的合并，但仅在前一个条目不相同时才添加条目。

您必须在合并后保留对最后一个包含数据的索引的引用，以便您可以在最后将数组大小调整为较小的数组并避免出现空单元格。

更新合并部分的一些精度:您将从两个已排序数组的开头开始，并在该索引处获取两项中较小的一项，然后增加您获取的数组的索引。考虑您的数组 a和b , target作为您的目标数组，i a 的索引光标, j对于 b和k对于 target :

1. 您从 i = j = k = 0 开始
2. 你拿v = min(a[i], b[j])并增加相关索引( i 如果您从 a 获取， j 如果您从 b 获取)
3. 如果 target[k-1] == v (当然当k > 0时)，您只需增加k (即忽略该值，因为它已经在数组中)
4. 否则你就这样做target[k++] = v (即将 v 放在 k 中的索引 target 处，然后递增 k )
5. 最后您将得到k等于目标数组的实际大小，因此您可以将数组修剪为大小为 k <= a.length + b.length 的数组

当然，在此过程中，一旦您耗尽了两个数组中的一个，您只需从另一个数组中获取并与 target 中的最后一个值进行比较即可。 .