尋找 Java 數組中最接近零的數字
1. 概述
在本教程中，我們將深入研究在 Java 數組中查找最接近零的數字的問題。例如，給定數組[1, -3, 2, -2, 4] ，最接近零的數字是1 。我們將探索各種技術來有效地找到這個數字並增強我們解決問題的能力。
2. 找出最接近零的數字的方法
我們將討論幾種方法，每種方法都有優點和缺點。首先，我們將了解暴力方法，然後是使用排序和二分搜尋的最佳化方法，最後是使用優先權佇列的替代技術。
2.1.蠻力方法
此方法涉及對數組的直接迭代，計算每個元素與零之間的絕對差，並追蹤迄今為止遇到的最小差。如果兩個數字與零的絕對差相同，則該方法會優先考慮正數，以確保結果一致且可預測。
讓我們從一個實作開始：
public static int findClosestToZero(int[] arr) throws IllegalAccessException {
if (arr == null || arr.length == 0) {
throw new IllegalAccessException("Array must not be null or Empty");
}
int closest = arr[0];
for (int i = 1; i < arr.length; i++) {
if ((Math.abs(arr[i]) < Math.abs(closest)) ||
((Math.abs(arr[i]) == Math.abs(closest)) && (arr[i] > closest))) {
closest = arr[i];
}
}
return closest;
}這種方法提供了一種基本但有效的方法來尋找整數陣列中最接近零的元素。讓我們透過一個測試來說明這一點：
@Test
void whenFindingClosestToZeroWithBruteForce_thenResultShouldBeCorrect()
throws IllegalAccessException {
int[] arr = {1, 60, -10, 70, -80, 85};
assertEquals(1, BruteForce.findClosestToZero(arr));
}2.2.使用排序和二分搜尋的方法
這種方法首先對數組進行排序，透過按元素絕對值的升序排列元素來簡化問題。排序後，應用二分搜尋演算法有效定位最接近零的元素。
我們看一下實作：
public static int findClosestToZero(int[] arr) {
if (arr == null || arr.length == 0) {
throw new IllegalArgumentException("Array must not be null or Empty");
}
Arrays.sort(arr);
int closestNumber = arr[0];
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (Math.abs(arr[mid]) < Math.abs(closestNumber)) {
closestNumber = arr[mid];
}
if (arr[mid] < 0) {
left = mid + 1;
} else if (arr[mid] > 0) {
right = mid - 1;
} else {
return arr[mid];
}
}
return closestNumber;
}此實作會對輸入數組進行排序，然後套用二分搜尋來檢查目前搜尋範圍的中間，縮小範圍以找到絕對值最小的數字。讓我們透過測試來驗證這一點：
@Test
void whenFindingClosestToZeroWithBruteForce_thenResultShouldBeCorrect() throws IllegalAccessException {
int[] arr = {1, 60, -10, 70, -80, 85};
assertEquals(1, SortingAndBinarySearch.findClosestToZero(arr));
}對於數組arr,演算法首先按升序排序，即[-80, -10, 1, 60, 70, 85] 。此方法將closestNumber初始化為第一個元素-80 ，並使用二分搜尋進行迭代。在第一次迭代中發現1比其他元素更接近 0 後，它會將closestNumber更新為1 。第一次迭代也會從原始數組[-80, -10, 1]產生此子數組。二分查找檢查中間元素並調整搜尋範圍直至退出，確認1是最接近 0 的。
2.3.使用優先權隊列的方法
另一種技術涉及利用優先權佇列來有效地找到最接近零的數字，而無需對整個數組進行排序。它通過將每個數字添加到隊列中並根據其絕對值僅保留最小的數字來找到最接近零的數字。
讓我們用 Java 實作這個方法：
public static int findClosestToZeroWithPriorityQueue(int[] arr, int k) {
if (arr == null || arr.length == 0 || k <= 0) {
throw new IllegalArgumentException("Invalid input");
}
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> Math.abs(b) - Math.abs(a));
for (int num : arr) {
pq.offer(num);
if (pq.size() > k) {
pq.poll();
}
}
return pq.peek();
}比較器Math.abs(b) – Math.abs(a)確保優先權佇列根據元素的絕對值對元素進行排序，距離零最遠的優先權最低。當我們迭代數組時，每個元素都會加入到優先權佇列中。如果佇列的大小超過k,則刪除離零最遠的元素，確保佇列僅保留第k個最接近零的數字。最後， pq.peek()傳回最接近零的元素。
我們來測試一下：
@Test
void whenFindingClosestToZeroWithBruteForce_thenResultShouldBeCorrect()
throws IllegalAccessException {
int[] arr = {1, 60, -10, 70, -80, 85};
assertEquals(1, PriorityQueueToZero.findClosestToZeroWithPriorityQueue(arr, 1));
}對於此測試，優先權佇列被初始化為僅保存一個元素，表示最接近零的數字。此演算法迭代數組[1, 60, -10, 70, -80, 85] ，依序處理每個元素。最初，由於隊列為空，因此將1新增至佇列。由於60與1相比離零更遠，因此不會添加它。當遇到-10時，不會添加它，因為1在絕對值上更接近零。與-10相比，後續元素70 、 -80和85都離零更遠，因此它們都不會添加到佇列中。處理完所有元素後，佇列保留1為最接近 0 的元素。
3.方法比較
雖然這三種方法都旨在找到 Java 數組中最接近零的數字，但它們表現出不同的特徵。
- 蠻力方法：雖然簡單，但由於其線性時間複雜度，對於較大的陣列來說，它變得越來越低效。
- 排序和二分搜尋的最佳化方法：它提供了更好的效能，特別是對於較大的數組，因為其時間複雜度為 O(n log n)，這明顯優於線性時間。然而，在某些情況下，對數組進行排序可能不可行，因此暴力方法更適合。
- 優先權佇列方法：它在簡單性和效能之間取得了平衡，使其適合於找到最接近數字的子集就足夠而對數組進行排序不可行的場景。
4。
在本文中，我們探討了解決在 Java 陣列中尋找最接近零的數字的問題的方法。
蠻力方法很簡單，對於小型數組效果很好，但對於較大的資料集就變得低效。
另一方面，排序和二分查找方法以 O(n log n) 的時間複雜度提高了效能，但可能不適合記憶體受限的場景。
最後，優先權佇列方法平衡了簡單性和效率，使其成為動態資料或記憶體有限情況的理想選擇。每種方法都有其優點，強調根據問題的特定要求選擇正確演算法的重要性。
本教程中使用的程式碼可在 GitHub 上取得。