在 Java 中尋找給定數組中缺少的數字
1. 概述
在 Java 陣列中尋找指定範圍內的缺失數字在各種場景中都很有用，例如資料驗證、確保完整性或識別資料集中的差距。
在本教程中，我們將學習多種方法從整數範圍[1-N]的陣列中尋找單一缺失數字。
2. 理解場景
假設我們已經得到了包含[1-9]範圍內的numbers數組（包括兩者）：
int[] numbers = new int[] { 1, 4, 5, 2, 7, 8, 6, 9 };現在，我們的目標是從陣列中找到[1-9]範圍內缺少的數字。
為了概括問題陳述，我們可以計算數組的長度並設定上限N ：
int N = numbers.length + 1;在以下部分中，我們將學習從[1-N]範圍內的給定數組中查找缺失數字的不同方法。
3. 使用算術和
讓我們先使用算術和來找出numbers數組中缺少的數字。
首先，我們將計算[1-N]範圍內算術級數的預期總和以及陣列的實際總和：
int expectedSum = (N * (N + 1)) / 2;
int actualSum = Arrays.stream(numbers).sum();接下來，我們可以從expectedSum中減去actualSum以獲得missingNumber ：
int missingNumber = expectedSum - actualSum;最後我們來驗證一下結果：
assertEquals(3, missingNumber);這是正確的！
4. 使用異或屬性
或者，我們可以使用異或運算子( ^ ) 的兩個有趣的屬性來解決我們的用例：
- X^X = 0：當我們將一個數字與其自身進行異或時，我們得到零。
- X^0 = X：當我們將數字與零進行異或時，我們會得到相同的數字。
首先，我們將使用reduce函數對封閉範圍[1-9]中的所有整數值進行異或運算：
int xorValue = IntStream.rangeClosed(1, N).reduce(0, (a, b) -> a ^ b);我們使用 0 和(a, b) -> a ^ b,這是一個 lambda 表達式）分別作為reduce()操作的標識和累加器。
接下來，我們將繼續對數字數組中的整數值進行異或運算：
xorValue = Arrays.stream(numbers).reduce(xorValue, (x, y) -> x ^ y);由於除了缺少數字之外的每個數字都會出現兩次，因此xorValue將只包含範圍[1-9]中的numbers數組中的缺失數字。
最後，我們應該驗證我們的方法是否給出了正確的結果：
assertEquals(3, xorValue);偉大的！我們做對了這一點。
5. 使用排序
我們的輸入數組， numbers,預計包含[1-N]範圍內的所有連續值，除了缺失的數字。因此，如果我們對數組進行排序，就可以很方便地在看不到連續數字的地方找到丟失的數字。
首先，我們將numbers數組進行排序：
Arrays.sort(numbers);接下來，我們可以迭代numbers數組並檢查index處的值是否為index+1 ：
int missingNumber = -1;
for (int index = 0; index < numbers.length; index++) {
if (numbers[index] != index + 1) {
missingNumber = index + 1;
break;
}
}當條件失敗時，表示數組中缺少預期值index + 1 。因此，我們設定了missingNumber並提前退出了循環。
最後，讓我們檢查是否獲得了所需的輸出：
assertEquals(3, missingNumber);結果看起來是正確的。但是，我們必須注意，在這種情況下我們改變了原始輸入陣列。
6. 使用boolean數組進行跟踪
在排序方法中，有兩個主要缺點：
- 分類的間接費用
- 原始輸入數組的變異
我們可以透過使用boolean數組來追蹤當前數字來緩解這些問題。
首先，我們將present定義為大小為N的boolean數組：
boolean[] present = new boolean[N];我們必須記住， N被初始化為numbers.length + 1 。
接下來，我們將迭代數字數組並標記present數組中每個數字的存在：
int missingNumber = -1;
Arrays.stream(numbers).forEach(number -> present[number - 1] = true);此外，我們將執行另一次迭代，但在present數組上，尋找未標記為存在的數字：
for (int index = 0; index < present.length; index++) {
if (!present[index]) {
missingNumber = index + 1;
break;
}
}最後，讓我們透過檢查missingNumber變數的值來驗證我們的方法：
assertEquals(3, missingNumber);完美的！我們的方法奏效了。此外，我們必須注意，我們使用了N位元組的額外空間，因為在 Java 中每個boolean值將佔用 1 個位元組。
7. 使用 Bitset 進行跟踪
我們可以透過在boolean數組上使用Bitset來優化空間複雜度。
BitSet bitSet = new BitSet(N);透過此初始化，我們將僅使用足夠的空間來表示N位元。當N的值相當高時，這是一個相當大的最佳化。
接下來，讓我們迭代numbers數組，並透過bitset:
for (int num : numbers) {
bitSet.set(num);
}現在，我們可以透過檢查未設定的位元來找到遺失的數字：
int missingNumber = bitSet.nextClearBit(1);最後，讓我們確認missingNumber中的值是否正確：
assertEquals(3, missingNumber);極好的！看起來我們已經解決了這個問題。
八、結論
在本教程中，我們學習如何從數組中找到缺少的數字。此外，我們探索了多種方法來解決用例，例如算術和、異或運算、排序以及其他資料結構，例如Bitset和boolean數組。
與往常一樣，本文中的程式碼可以在 GitHub 上取得。