從 Java 整數列表中尋找最接近給定值的數字

1. 概述

當我們在 Java 中使用整數List時，我們可能遇到的常見問題是在List中尋找最接近給定值的數字。

在本教程中，我們將探索使用 Java 解決此問題的不同方法。

2.問題介紹

我們先來看看問題的定義：

給定一個整數List和一個target ，我們需要從List中找到最接近target的數字。如果多個數字同樣接近，我們會選擇索引最低的數字。

接下來，讓我們快速了解數字與給定target.

2.1.兩個數字之間的距離

在這種情況下，數字a和b之間的距離是a – b的絕對值： Distance = abs(a – b)

例如，給定target = 42, the以下是target與不同數字 ( n ) 之間的距離 ( D )：

• n = 42 → D = abs(42 – 42) = 0
• n = 100 → D = abs(42 – 100) = 58
• n = 44 → D = abs(42 – 44) = 2
• n = 40 → D = abs(42 – 40) = 2

我們可以看到，給定target = 42，數字 44 和 40 到target的距離相同。

2.2.了解問題

因此， **List**中距離**the target**最近的數字**在所有元素中與**target****的距離最小。例如，在List中：

[ 8, 100, 6, 89, -23, 77 ]

給定target = 70 target = 7 List中最接近它的整數是 77。在這種情況下，我們選擇索引最低的數字。因此，8 是預期結果。

為簡單起見，我們假設給定的List不為null或empty 。我們將探索解決此問題的各種方法。我們也將以此整數List為例，並利用單元測試斷言來驗證每個解決方案的結果。

此外，為了有效地解決問題，我們將根據輸入List是否已排序選擇不同的演算法來解決問題。

接下來，我們設計一些測試案例來涵蓋所有場景：

• 當target （-100）小於最小值時。 List中的整數 (-23) : result = -23
• 當target (500) 大於最大值時。 List中的整數 (100)： result = 100
• 當List中存在target (89) 時： result = 89
• 當List中不存在target (70) 時： result = 77
• 如果List中的多個整數（8 和 6）到target (7) 的距離 (1) 相同： result = 8

現在，讓我們深入研究程式碼。

3. 當我們不知道List是否已排序時

通常，我們不知道給定的List是否已排序。因此，讓我們創建一個List變數來保存我們的數字：

static final List<Integer> UNSORTED_LIST = List.of(8, 100, 6, 89, -23, 77);

顯然，這不是一個排序List.

接下來，我們將使用兩種不同的方法來解決這個問題。

3.1.使用循環

解決問題的第一個想法是遍歷List並檢查每個數字與target之間的距離：

static int findClosestByLoop(List<Integer> numbers, int target) {

 int closest = numbers.get(0);

 int minDistance = Math.abs(target - closest);

 for (int num : numbers) {

 int distance = Math.abs(target - num);

 if (distance < minDistance) {

 closest = num;

 minDistance = distance;

 }

 }

 return closest;

 }

如程式碼所示，我們從List中closest,並將**target與其之間的距離保存在另一個變數minDistance中，該變數追蹤最小距離**。

然後，我們循環遍歷List 。對於List中的每個數字，我們計算其到target距離並將其與minDistance.如果它小於minDistance,我們會更新closest和minDistance.

迭代整個List後， closest保存最終結果。

接下來，讓我們建立一個測試來檢查此方法是否按預期工作：

assertEquals(-23, findClosestByLoop(UNSORTED_LIST, -100));

 assertEquals(100, findClosestByLoop(UNSORTED_LIST, 500));

 assertEquals(89, findClosestByLoop(UNSORTED_LIST, 89));

 assertEquals(77, findClosestByLoop(UNSORTED_LIST, 70));

 assertEquals(8, findClosestByLoop(UNSORTED_LIST, 7));

正如我們所看到的，這個基於循環的解決方案通過了我們所有的測試案例。

3.2.使用流 API

Java Stream API 使我們能夠方便、簡潔地處理集合。接下來，我們使用 Stream API 來解決這個問題：

static int findClosestByStream(List<Integer> numbers, int target) {

 return numbers.stream()

 .min(Comparator.comparingInt(o -> Math.abs(o - target)))

 .get();

 }

該程式碼看起來比基於循環的解決方案更緊湊。讓我們快速瀏覽一下它以了解它是如何工作的。

首先， numbers.stream()將List<Integer>轉換為Stream<Integer> 。

然後， min()根據自訂的 Comparator 尋找Stream中的最小元素Comparator.在這裡，我們使用Comparator.comparingInt()和 lambda 表達式來建立自訂Comparator ，該比較器根據 lambda 產生的值來比較整數。 lambda o -> Math.abs(o – target)有效地測量target與List.

min()操作傳回一個Optional 。由於我們假設List不為空，因此Optional始終存在。因此，我們直接呼叫get()從Optional物件中提取最接近的數字。

接下來，讓我們檢查基於流的方法是否正常運作：

assertEquals(-23, findClosestByStream(UNSORTED_LIST, -100));

 assertEquals(100, findClosestByStream(UNSORTED_LIST, 500));

 assertEquals(89, findClosestByStream(UNSORTED_LIST, 89));

 assertEquals(77, findClosestByStream(UNSORTED_LIST, 70));

 assertEquals(8, findClosestByStream(UNSORTED_LIST, 7));

如果我們運行測試，它就會通過。因此，該解決方案簡潔有效地完成了這項工作。

3.3.表現

無論是應用簡單的基於循環的方法還是緊湊的基於流的方法，我們都必須迭代整個List一次才能獲得結果。因此，兩種解具有相同的時間複雜度： O(n) 。

由於這兩個解決方案都沒有考慮List順序, 無論給定的L是否已排序，它們都會**ist** 。

但是，如果我們知道輸入List已排序，我們可以應用不同的演算法以獲得更好的效能。接下來，讓我們弄清楚如何做。

4. List排序時

如果List是有順序的，我們可以使用O(log n)複雜度的二分查找來提高效能。

首先，讓我們建立一個包含前面範例中相同數字的排序List ：

static final List<Integer> SORTED_LIST = List.of(-23, 6, 8, 77, 89, 100);

然後，我們可以實作一個基於二分搜尋的方法來解決這個問題：

public static int findClosestByBiSearch(List<Integer> sortedNumbers, int target) {

 int first = sortedNumbers.get(0);

 if (target <= first) {

 return first;

 }



 int last = sortedNumbers.get(sortedNumbers.size() - 1);

 if (target >= last) {

 return last;

 }



 int pos = Collections.binarySearch(sortedNumbers, target);

 if (pos > 0) {

 return sortedNumbers.get(pos);

 }

 int insertPos = -(pos + 1);

 int pre = sortedNumbers.get(insertPos - 1);

 int after = sortedNumbers.get(insertPos);



 return Math.abs(pre - target) <= Math.abs(after - target) ? pre : after;

 }

現在，讓我們了解程式碼是如何運作的。

首先，我們處理兩種特殊情況：

• target <= List中最小的數字，即第一個元素 – 傳回第一個元素
• target >= List中最大的數字，即最後一個元素 – 傳回最後一個元素

然後，我們呼叫Collections.binarySearch()來找出target在已排序 List 中的位置 ( pos ) **List** . binarySearch()返回：

• pos > 0 – 完全匹配，這意味著在List中找到target
• pos < 0 – 未找到target 。負pos是取反的插入點（將插入target以維持排序順序）減去 1： pos = (- insertPos – 1)

如果找到精確匹配，我們會直接取得匹配，因為它是最接近target的數字（ distance = 0 ） 。

否則，我們需要從插入點前後的兩個數字中確定closest數字(insertionPos = – (pos – 1)).當然，距離較小的數字獲勝。

該方法通過了相同的測試案例：

assertEquals(-23, findClosestByBiSearch(SORTED_LIST, -100));

 assertEquals(100, findClosestByBiSearch(SORTED_LIST, 500));

 assertEquals(89, findClosestByBiSearch(SORTED_LIST, 89));

 assertEquals(77, findClosestByBiSearch(SORTED_LIST, 70));

 assertEquals(6, findClosestByBiSearch(SORTED_LIST, 7));

值得注意的是，給定target = 7 ，最後一個斷言中的預期數字是 6 而不是 8 。這是因為在已排序的List中，6 的索引 (1) 小於 8 的索引 (2)。

5. 結論

在本文中，我們探索了兩種從整數List中找到最接近給定值的數字的方法。此外，如果List已排序，我們可以使用二分搜尋來有效地找到最接近的數字，時間複雜度為O(log n) 。

與往常一樣，範例的完整原始程式碼可在 GitHub 上取得。