Java：如何为非重复元素比较两个int []数组？

Question

如何比较重复元素的两个int []数组？

例如：int countDifference(int[] arrayA, int[] arrayB)以输入两个有序数组数组为例，返回两个数组中只有一个数组中出现的数字个数。

实施例：countdifference（[2,4,6,8]，[3,4,6,9]）返回4因为4和6是重复的，其余的数字是2，8，3和9。

我得到了一个方法来计算不同的元素为一个数组工作，但不是两个数组的非重复元素。

import java.util.HashSet; 
import java.util.Set; 

public class countDistinctArray { 

    public static int distinctNumberOfItems(int[] array) { 
    if (array.length <= 1) { 
     return array.length; 
    } 

    Set<Integer> set = new HashSet<Integer>(); 
    for (int i : array) { 
     set.add(i); 
    } 
    return set.size(); 
    } 

    public static void main(String args[]) { 
    int array[] = { 2, 4, 6, 8, 3, 4, 6, 9 }; 
    System.out.println(distinctNumberOfItems(array)); 
    } 
} 

Answer 1

您可以使用二分查找来比较数组并找出差异。你需要做的是比较，因为双向（< - - >），如：

array1 --> array2 and array2 --> array1 

因为你需要总结的组差异。设A和B为我们的集合，我们需要找到：

(A-B) U (B-A) 

二进制搜索解决方案如下。该算法的复杂度为O（log n）的

private static int getDifferenceBetweenTwoArray(int[] array1 , int[] array2) 
{ 
    int differenceCount = 0; 
    //if you dont want to sort your original arrays, create temporary arrays 
    int temp1[] = Arrays.copyOf(array1 , array1.length); 
    int temp2[] = Arrays.copyOf(array2 , array2.length); 
    Arrays.sort(temp1); 
    Arrays.sort(temp2); 

    for(Integer i : temp1) 
    { 
     if(Arrays.binarySearch(temp2, i) < 0) 
      differenceCount++; 
    } 
    for(Integer i: temp2) 
    { 
     if(Arrays.binarySearch(temp1, i) < 0) 
      differenceCount++; 
    } 

    return differenceCount; 
} 

Answer 2

这可能会实现

 int countDifference(int[] arrayA, int[] arrayB){ 
     int count=0;   
     for(int i=0;i<arrayA.length;i++){ 
      for(int j=0;j<arrayB.length){ 
      if(arrayA[i]==arrayB[j]) 
      count++; 
      else 
      continue;}} }  

Answer 3

一种方式做到这一点，是为使用的Set的removeAll()或retainAll()方法。另一种方法是并行迭代阵列，不使用Set。

易于使用的，前两种方法会使用这个帮手：

private static Set<Integer> asSet(int[] array) { 
    Set<Integer> set = new HashSet<>(); 
    for (int i : array) 
     set.add(i); 
    return set; 
} 

使用removeAll()实现：

public static int countDifference(int[] array1, int[] array2) { 
    // Find distinct elements in array1 that doesn't exist in array2 
    Set<Integer> distinct1 = asSet(array1); 
    distinct1.removeAll(asSet(array2)); 

    // Find distinct elements in array2 that doesn't exist in array1 
    Set<Integer> distinct2 = asSet(array2); 
    distinct2.removeAll(asSet(array1)); 

    return distinct1.size() + distinct2.size(); 
} 

如果本身保证了阵列不包含重复，然后retainAll()能找到常见值：

public static int countDifference(int[] array1, int[] array2) { 
    Set<Integer> common = asSet(array1); 
    common.retainAll(asSet(array2)); 
    return array1.length + array2.length - 2 * common.size(); 
} 

上述两种实现都不依赖于正在排序的数组。为了消除创建集的开销和所有值的拳击，你可以使用数组的排序，并且并行迭代他们：

public static int countDifference(int[] array1, int[] array2) { 
    int idx1 = 0, idx2 = 0, count = 0, val; 
    while (idx1 < array1.length || idx2 < array2.length) { 
     if (idx1 == array1.length) { 
      val = array2[idx2]; 
      count++; 
     } else if (idx2 == array2.length) { 
      val = array1[idx1]; 
      count++; 
     } else { 
      val = Math.min(array1[idx1], array2[idx2]); 
      if (array1[idx1] != val || array2[idx2] != val) 
       count++; 
     } 
     while (idx1 < array1.length && array1[idx1] == val) 
      idx1++; // skipping 0 to many instances of val in array1 
     while (idx2 < array2.length && array2[idx2] == val) 
      idx2++; // skipping 0 to many instances of val in array2 
    } 
    return count; 
} 

这将是最快，最内存高效的实现。

---

思想

这可以说是countDifference会考虑投入3,5,5,7和3,5,7有1个差异。如果是这样，那么任何使用Set是错误的，最后的方法应该if语句替换内while循环，或者使用更简单的实现是这样的：

public static int countDifference(int[] array1, int[] array2) { 
    int idx1 = 0, idx2 = 0, count = 0; 
    while (idx1 < array1.length && idx2 < array2.length) { 
     int cmp = Integer.compare(array1[idx1], array2[idx2]); 
     if (cmp != 0) 
      count++; 
     if (cmp <= 0) 
      idx1++; 
     if (cmp >= 0) 
      idx2++; 
    } 
    return count + (array1.length - idx1) + (array2.length - idx2); 
} 

就个人而言，我认为这是正确的解决方案，但这取决于应该如何处理数组中的重复值。如果不存在重复，或者重复被认为是不同的，则这是最好的实施方式，例如，就像上面这个例子中的值5一样。

Answer 4

如果性能是不是一个问题，并使用Java的数据结构，如HashSet的是允许的，并考虑到在阵列数字是按升序排列，然后在这里是一个简单的解决方案： 首先我们将第二个数组的所有元素放入一个哈希集中，然后循环遍历第一个数组，以查看两个数组共有多少个元素，然后返回两个数组中元素的总数，减去那些常见的元件

import java.util.*; 

public class CountDistinctArrays { 
    public static void main(String[] args) { 
     int[] arrayOne = new int[]{-1, 1, 3, 4, 6, 7, 8}; 
     int[] arrayTwo = new int[]{1, 2, 3, 4, 5}; 

     System.out.println(distinctNumberOfItems(arrayOne, arrayTwo)); 
    } 

    public static int distinctNumberOfItems(int[] first, int[] second) { 
     Set<Integer> numbers = new HashSet<Integer>(); 
     for (int num : second) { 
      numbers.add(num); 
     } 

     int commonElements = 0; 
     for (int num : first) { 
      if (numbers.contains(num)) { 
       commonElements++; 
      } 
     } 

     return first.length + second.length - commonElements * 2; 
    } 

}