在 Java 中合併兩個陣列並刪除重複項
1. 概述
在本教程中，我們將探索合併兩個陣列的內容並隨後消除重複項的各種方法。它類似於聯合操作：
- 數組1
Union數組2
為此，我們將考慮兩個整數數組。基本上，如果以下是兩個陣列：
- arr1 = { 3, 2, 1, 4, 5, 6, 8, 7, 6, 9 }
- arr2 = { 8, 9, 10, 11, 12, 13, 15, 14, 15, 14, 16, 17 }
那麼結果應該是：
- 合併陣列 = { 3, 2, 1, 4, 5, 6, 8, 7, 9, 10, 11, 12, 13, 14, 15, 16, 17 }
2. 基本數組運算的方法
通常，這個需求可以透過使用Set或Stream API 來實現，後面的章節將對此進行解釋。但這些圖書館是資源密集的。因此，我們將更專注於傳統方法，在迭代過程中使用基本數組操作。
2.1.未排序數組的方法
首先，讓我們定義一個合併數組的函數。然後，我們將建立一個方法來從中刪除重複項。或者，我們可以從陣列中刪除重複項，然後合併它們。但這不會對性能產生太大影響。
因此，讓我們從合併兩個陣列的方法開始：
static int[] mergeArrays(int[] arr1, int[] arr2) {
int[] mergedArrays = new int[arr1.length + arr2.length];
System.arraycopy(arr1, 0, mergedArrays, 0, arr1.length);
System.arraycopy(arr2, 0, mergedArrays, arr1.length, arr2.length);
return mergedArrays;
}接下來，我們將使用上述方法來合併所有部分中的陣列。
現在，讓我們實作從合併數組中刪除重複項的方法：
static int[] removeDuplicate(int[] arr) {
int[] withoutDuplicates = new int[arr.length];
int i = 0;
for (int element : arr) {
if (!isElementPresent(withoutDuplicates, element)) {
withoutDuplicates[i] = element;
i++;
}
}
int[] truncatedArray = new int[i];
System.arraycopy(withoutDuplicates, 0, truncatedArray, 0, i);
return truncatedArray;
}
static boolean isElementPresent(int[] arr, int element) {
for (int el : arr) {
if (el == element) {
return true;
}
}
return false;
}在上述方法中，在removeDuplicate()中，僅當元素不預先存在於withoutDuplicates陣列中時，才會使用合併陣列的元素填入該陣列。
透過使用上述方法，我們定義mergeAndRemoveDuplicates() ：
public static int[] mergeAndRemoveDuplicates(int[] arr1, int[] arr2) {
return removeDuplicate(mergeArrays(arr1, arr2));
}讓我們看看它是如何運作的：
@Test
public void givenNoLibraryAndUnSortedArrays_whenArr1andArr2_thenMergeAndRemoveDuplicates() {
int[] arr1 = {3, 2, 1, 4, 5, 6, 8, 7, 9};
int[] arr2 = {8, 9, 10, 11, 12, 13, 15, 14, 15, 14, 16, 17};
int[] expectedArr = {3, 2, 1, 4, 5, 6, 8, 7, 9, 10, 11, 12, 13, 15, 14, 16, 17};
int[] mergedArr = MergeArraysAndRemoveDuplicate.mergeAndRemoveDuplicates(arr1, arr2);
assertArrayEquals(expectedArr, mergedArr);
}證明我們達到了預期的效果。有趣的是，這種方法也保留了數組元素的順序。
由於刪除重複項涉及將合併數組中的每個元素與所有其他元素進行比較，因此此方法的時間複雜度接近 O(nxn)。
2.2.排序數組的方法
讓我們考慮一個場景，其中元素已在數組中排序。在這種情況下，我們可以使用以下方法來去除重複元素：
public static int[] removeDuplicateOnSortedArray(int[] arr) {
int[] uniqueArray = new int[arr.length];
uniqueArray[0] = arr[0];
int uniqueCount = 1;
for (int i = 1; i < arr.length; i++) {
if (arr[i] != arr[i - 1]) {
uniqueArray[uniqueCount] = arr[i];
uniqueCount++;
}
}
int[] truncatedArray = new int[uniqueCount];
System.arraycopy(uniqueArray, 0, truncatedArray, 0, uniqueCount);
return truncatedArray;
}這種方法更有效，因為它只比較相鄰元素。如果它們不相等，則將它們新增至uniqueArray數組。相反，先前的isElementPresent()方法將陣列元素與陣列中的所有其他元素進行比較。
讓我們來看看removeDuplicateOnSortedArray()實際效果：
@Test
public void givenNoLibraryAndSortedArrays_whenArr1andArr2_thenMergeAndRemoveDuplicates() {
int[] arr1 = {1, 2, 3, 4, 5, 5, 6, 7, 7, 8};
int[] arr2 = {8, 9, 10, 11, 12, 13, 14, 15, 15, 16, 17};
int[] expectedArr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17};
int[] mergedArr = MergeArraysAndRemoveDuplicate.mergeAndRemoveDuplicatesOnSortedArray(arr1, arr2);
assertArrayEquals(expectedArr, mergedArr);
}在最壞的情況下，此方法的時間複雜度為 O(n)。
3. 使用Set合併數組
S et不允許重複元素。因此，此功能有助於刪除重複項。
讓我們來看看mergeAndRemoveDuplicatesUsingSet()方法：
public static int[] mergeAndRemoveDuplicatesUsingSet(int[] arr1, int[] arr2) {
int[] mergedArr = mergeArrays(arr1, arr2);
Set<Integer> uniqueInts = new HashSet<>();
for (int el : mergedArr) {
uniqueInts.add(el);
}
return getArrayFromSet(uniqueInts);
}將陣列元素新增至Set uniqueInts時，如果這些元素在 init 中已存在，則會被忽略。最後， getArrayFromSet()將Set轉換為陣列。
讓我們看看上面的方法的表現如何：
@Test
public void givenSet_whenArr1andArr2_thenMergeAndRemoveDuplicates() {
int[] arr1 = {3, 2, 1, 4, 5, 6, 8, 7, 9};
int[] arr2 = {8, 9, 10, 11, 12, 13, 15, 14, 15, 14, 16, 17};
int[] expectedArr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17};
int[] mergedArr = MergeArraysAndRemoveDuplicate.mergeAndRemoveDuplicatesUsingSet(arr1, arr2);
assertArrayEquals(expectedArr, mergedArr);
}很明顯。數組不再保留元素的順序。
這種方法的執行時間取決於數組元素的數量。因此，其時間複雜度為O(n)。
4. 使用Stream合併數組
強大的Stream API 提供了一種非常簡潔且聲明性的方式來合併和刪除陣列中的重複項。有關更多詳細信息，讓我們查看方法mergeAndRemoveDuplicatesUsingStream() ：
public static int[] mergeAndRemoveDuplicatesUsingStream(int[] arr1, int[] arr2) {
Stream<Integer> s1 = Arrays.stream(arr1).boxed();
Stream<Integer> s2 = Arrays.stream(arr2).boxed();
return Stream.concat(s1, s2)
.distinct()
.mapToInt(Integer::intValue)
.toArray();
}首先，將陣列單獨轉換為Stream 。然後， boxed 方法將陣列中的int元素包裝為Integer 。此外， Stream管道合併數組，然後消除其中的重複項。
讓我們看看它是如何運作的：
@Test
public void givenStream_whenArr1andArr2_thenMergeAndRemoveDuplicates() {
int[] arr1 = {3, 2, 1, 4, 5, 6, 8, 7, 9};
int[] arr2 = {8, 9, 10, 11, 12, 13, 15, 14, 15, 14, 16, 17};
int[] expectedArr = {3, 2, 1, 4, 5, 6, 8, 7, 9, 10, 11, 12, 13, 15, 14, 16, 17};
int[] mergedArr = MergeArraysAndRemoveDuplicate.mergeAndRemoveDuplicatesUsingStream(arr1, arr2);
assertArrayEquals(expectedArr, mergedArr);
}很明顯，Stream 方法保留了陣列中元素的順序。
決定時間複雜度的主導因素是流中的distinct()方法，它是O(n)。總的來說，我們可以說這種方法的時間複雜度是O(n)。
5. 結論
在本教程中，我們研究了合併兩個數組然後從中刪除重複項的各種方法。最簡潔的方法是使用Stream API。套裝 不保留插入其中的元素的順序。然而， Set在刪除重複項方面非常有效。其他兩種方法保留數組中元素的順序。
值得注意的是， Stream和Set非常消耗資源，因此建議盡可能避免使用它們。
與往常一樣，程式碼範例可以在 GitHub 上找到。