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

}