尋找 Java 數組中差異最大的元素
一、簡介
在本教程中，我們將探索不同的方法來尋找 Java 整數陣列中任兩個元素之間的最大差異。我們將使用一個包含 10 個範圍從 -10 到 10 的隨機整數的範例陣列來演示該問題。然後，我們將探索不同的演算法來解決這個問題，從簡單的方法開始，逐漸轉向更優化的解決方案。
2. 問題定義
在尋找數組中兩個元素之間的最大差異有許多實際應用。例如，在數據分析中，我們需要確定數據點之間的最大差異，而在股票價格分析中，我們需要計算買入價和賣出價之間的最大利潤。在遊戲開發中，我們也需要計算不同點（例如，玩家位置或得分）之間的最大距離。
給定一個整數數組，我們的任務是識別具有最大絕對差異的元素，以及它們相應的索引，以及這些索引指向的值。我們將探索解決此問題的幾種方法，每種方法都有不同的時間和空間複雜度。
3. 蠻力方法
蠻力方法是最簡單、最直覺的。我們比較每對可能的元素來計算它們的差異。此方法的時間複雜度為O(n^2) ，因此對於大型陣列來說效率低：
public static int[] findMaxDifferenceBruteForce(int[] list) {
int maxDifference = Integer.MIN_VALUE;
int minIndex = 0, maxIndex = 0;
for (int i = 0; i < list.length - 1; i++) {
for (int j = i + 1; j < list.length; j++) {
int difference = Math.abs(list[j] - list[i]);
if (difference > maxDifference) {
maxDifference = difference;
minIndex = i;
maxIndex = j;
}
}
}
int[] result = new int[] { minIndex, maxIndex, list[minIndex], list[maxIndex], maxDifference };
return result;
}這種方法檢查每一對元素，使其實現簡單但效率低。儘管它顯示的空間複雜度為O(1) ，但對於較大的數組， O(n^2)時間複雜度使其不切實際。該方法迭代所有元素對以確定最大差異。
我們將使用數組測試我們的方法，如下所示：
@Test
public void givenAnArray_whenUsingBruteForce_thenReturnCorrectMaxDifferenceInformation() {
int[] list = {3, -10, 7, 1, 5, -3, 10, -2, 6, 0};
int[] result = MaxDifferenceBruteForce.findMaxDifferenceBruteForce(list);
assertArrayEquals(new int[]{1, 6, -10, 10, 20}, result);
}TreeSet （平衡樹）方法
更進階的方法是使用[TreeSet](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/TreeSet.html)來維護動態排序的元素集合。這使得我們能夠在遍歷過程中快速檢索最小和最大元素：
public static int[] findMaxDifferenceTreeSet(int[] list) {
TreeSet<Integer> set = new TreeSet<>();
for (int num : list) {
set.add(num);
}
int minValue = set.first();
int maxValue = set.last();
int minIndex = 0;
int maxIndex = list.length - 1;
for (int i = 0; i < list.length; i++) {
if (list[i] == minValue) {
minIndex = i;
} else if (list[i] == maxValue) {
maxIndex = i;
}
}
int maxDifference = Math.abs(maxValue - minValue);
int[] result = new int[] { minIndex, maxIndex, list[minIndex], list[maxIndex], maxDifference };
return result;
}使用TreeSet可以在O(n*log(n))時間內動態更新並有效檢索最小值和最大值。然而，此解決方案需要儲存整個數組，因此空間複雜度為O(n) 。
我們也在TreeSet實作上執行相同的測試用例：
@Test
public void givenAnArray_whenUsingTreeSet_thenReturnCorrectMaxDifferenceInformation() {
int[] list = {3, -10, 7, 1, 5, -3, 10, -2, 6, 0};
int[] result = MaxDifferenceTreeSet.findMaxDifferenceTreeSet(list);
assertArrayEquals(new int[]{1, 6, -10, 10, 20}, result);
}5. 優化的單通道方法
為了提高效率，我們可以遍歷數組一次，同時追蹤最小值，如果當前差值更大，則更新最大差值。這將時間複雜度降低到O(n)同時仍將空間複雜度保持為O(1) ：
public static int[] findMaxDifferenceOptimized(int[] list) {
int minElement = list[0];
int maxElement = list[0];
int minIndex = 0;
int maxIndex = 0;
for (int i = 1; i < list.length; i++) {
if (list[i] < minElement) {
minElement = list[i];
minIndex = i;
}
if (list[i] > maxElement) {
maxElement = list[i];
maxIndex = i;
}
}
int maxDifference = Math.abs(maxElement - minElement);
int[] result = new int[] { minIndex, maxIndex, list[minIndex], list[maxIndex], maxDifference };
return result;
}這種方法效率更高。它迭代數組一次，更新最小元素並動態計算最大差異。此方法產生與暴力方法相同的結果，但時間複雜度為O(n) ，使其適合大型陣列。
我們透過使用相同的輸入來運行測試並期望相同的輸出來測試實現的正確性，就像暴力方法一樣：
@Test
public void givenAnArray_whenUsingOptimizedOnePass_thenReturnCorrectMaxDifferenceInformation() {
int[] list = {3, -10, 7, 1, 5, -3, 10, -2, 6, 0};
int[] result = MaxDifferenceOptimized.findMaxDifferenceOptimized(list);
assertArrayEquals(new int[]{1, 6, -10, 10, 20}, result);
}6. 常見陷阱
以下是這個問題中可能出現的一些陷阱：
- 處理具有相同最大差異的多個對：所提出的每種方法僅傳回具有最大差異的一對索引，儘管可能存在多個有效對。
- 輸入約束：在輸入值具有已知約束的情況下，一旦遇到最大可能的差異，可以透過停止來實現提前終止。
- 負值和絕對差值：雖然我們解決了這個問題，但值得一提的是，當最大和最小元素均為負數時，必須以絕對值計算差值以確保正確性。
七、結論
在本教程中，我們探索了多種方法來尋找數組中兩個元素之間的最大差異。我們從簡單但效率低下的強力解決方案開始，並逐漸發展到更優化的方法。
優化的單遍方法對於這個問題是最有效的，提供了O(n)的時間複雜度和最小的空間使用。我們也探索了TreeSet方法，該方法以空間和時間複雜度的性能為代價提供了靈活性。
本文的完整原始碼可以在 GitHub 上找到。