检查两个整数数组是否有重复元素，并从它们中提取其中一个重复元素

Question

我正在尝试编写一个名为union()的方法，它将返回一个int数组，并且需要两个int数组参数，检查它们是否是集合，换句话说，它们之间是否有重复项。我已经写了另一个方法isSet()，它需要一个数组参数并检查该数组是否是一个集合。问题是，我想在union方法中检查这两个数组是否有重复项，如果有，我想提取其中一个重复项并将其放入unionArray[] int数组中。这是我目前尝试过的。

public int[] union(int[] array1, int[] array2){
  
  int count = 0;
  if (isSet(array1) && isSet(array2)){
     for (int i = 0; i < array1.length; i++){
        for (int j = 0; j < array2.length; j++){
           if (array1[i] == array2[j]){ 
              System.out.println(array2[j]);
              count ++;
           }
        }
     }
  }
  int[] array3 = new int[array2.length - count];
     
  int[] unionArray = new int[array1.length + array3.length];
  int elementOfUnion = 0;
      
  for (int i = 0; i< array1.length; i++){
     unionArray[i] = array1[i];
     elementOfUnion = i + 1 ;
  }
  int index = 0;
  for (int i = elementOfUnion; i < unionArray.length; i++){
     unionArray[i] = array3[index];
     index++;
  }
  
  
  return unionArray;
}


public boolean isSet(int[] array){
  boolean duplicates = true;
  
  for (int i = 0; i < array.length; i++){
     for(int n = i+1; n < array.length; n++){
        if (array[i] == array[n])
           duplicates = false;
     }
  }
     
  return duplicates;
}

我想做的是将array1的所有元素用于unionArray中，检查array2是否有与array1重复的元素，然后将array2中所有非重复元素移动到一个新的数组array3中，并将array3连接到unionArray中。

- Laith.jas

Answer 1

使用Java的流可以使这个过程更简单：

public int[] union(int[] array1, int[] array2) {
    return Stream.of(array1, array2).flatMapToInt(Arrays::stream).distinct().toArray();
}

- Mureinik

---

对不起，我应该提到这是一项课堂作业，所以我不能使用其他方法，我只能使用最基本的东西，或者我必须编写自己的方法。 - Laith.jas

Answer 2

使用 Collection API 或 Stream API 将更容易实现。但是，您已经提到想要纯粹使用数组且不导入任何类，这将需要一些冗长（尽管简单）的处理单元。驱动逻辑最重要的理论是如何计算联合（如下所示）：

n(A U B) = n(A) + n(B) - n(A ∩ B)

并且

n(Only A) = n(A) - n(A ∩ B)
n(Only B) = n(B) - n(A ∩ B)

这个解决方案的高级摘要如下图所示：

代码中的注释已经非常清楚地说明了其余的逻辑。

public class Main {
    public static void main(String[] args) {
        // Test
        display(union(new int[] { 1, 2, 3, 4 }, new int[] { 3, 4, 5, 6 }));
        display(union(new int[] { 1, 2, 3 }, new int[] { 4, 5, 6 }));
        display(union(new int[] { 1, 2, 3, 4 }, new int[] { 1, 2, 3, 4 }));
        display(union(new int[] { 1, 2, 3, 4 }, new int[] { 3, 4 }));
        display(union(new int[] { 1, 2, 3, 4 }, new int[] { 4, 5 }));
        display(union(new int[] { 1, 2, 3, 4, 5, 6 }, new int[] { 7, 8 }));
    }

    public static int[] union(int[] array1, int[] array2) {
        // Create an array of the length equal to that of the smaller of the two array
        // parameters
        int[] intersection = new int[array1.length <= array2.length ? array1.length : array2.length];
        int count = 0;

        // Put the duplicate elements into intersection[]
        for (int i = 0; i < array1.length; i++) {
            for (int j = 0; j < array2.length; j++) {
                if (array1[i] == array2[j]) {
                    intersection[count++] = array1[i];
                }
            }
        }

        // Create int []union of the length as per the n(A U B) = n(A) + n(B) - n(A ∩ B)
        int[] union = new int[array1.length + array2.length - count];

        // Copy array1[] minus intersection[] into union[]
        int lastIndex = copySourceOnly(array1, intersection, union, count, 0);

        // Copy array2[] minus intersection[] into union[]
        lastIndex = copySourceOnly(array2, intersection, union, count, lastIndex);

        // Copy intersection[] into union[]
        for (int i = 0; i < count; i++) {
            union[lastIndex + i] = intersection[i];
        }

        return union;
    }

    static int copySourceOnly(int[] source, int[] exclude, int[] target, int count, int startWith) {
        int j, lastIndex = startWith;
        for (int i = 0; i < source.length; i++) {
            // Check if source[i] is present in intersection[]
            for (j = 0; j < count; j++) {
                if (source[i] == exclude[j]) {
                    break;
                }
            }

            // If j has reached count, it means `break;` was not executed i.e. source[i] is
            // not present in intersection[]
            if (j == count) {
                target[lastIndex++] = source[i];

            }
        }
        return lastIndex;
    }

    static void display(int arr[]) {
        System.out.print("[");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(i < arr.length - 1 ? arr[i] + ", " : arr[i]);
        }
        System.out.println("]");
    }
}

输出：

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

- Arvind Kumar Avinash

Answer 3

即使只使用数组，您也可以大大简化代码。无需检查集合。只需执行以下操作：

1. 分配一个数组以存储联合的所有元素（即int[] tmp_union），最坏情况下将是来自array1和array2两个数组的所有元素。
2. 遍历array1的元素并将它们与tmp_union数组中的元素进行比较，仅在尚未添加到该数组中时将其添加到tmp_union数组中。
3. 对于array2，重复步骤2）。

在此过程中，跟踪到目前为止添加到tmp_union数组中的元素数量（即added_so_far）。最后，将tmp_union数组中的元素复制到新数组（即unionArray）中，该数组仅为联合元素分配了空间。代码如下：

public static int[] union(int[] array1, int[] array2){
    int[] tmp_union = new int[array1.length + array2.length];
    int added_so_far = add_unique(array1, tmp_union, 0);
        added_so_far = add_unique(array2, tmp_union, added_so_far);
    return copyArray(tmp_union, added_so_far);
}

private static int[] copyArray(int[] ori, int size) {
    int[] dest = new int[size];
    for(int i = 0; i < size; i++)
        dest[i] = ori[i];
    return dest;
}

private static int add_unique(int[] array, int[] union, int added_so_far) {
    for (int element : array)
        if (!is_present(union, added_so_far, element))
            union[added_so_far++] = element;
    return added_so_far;
}

private static boolean is_present(int[] union, int added_so_far, int element) {
    for (int z = 0; z < added_so_far; z++)
         if (element == union[z])
             return true;
    return false;
}

- dreamcrash