從無序整數列表中查詢最接近的數字

---

在下面的文章中，我們將討論兩種從無序整數列表中查詢最接近數字的方法。讓我們首先了解“最接近數字”的含義。“最接近數字”是指差異最小的數字對。

問題陳述

給定一個不同的無序整數列表，我們需要找到差異最小的元素對。如果有多個對，我們需要找到所有對。此外，在本文中，只要提到差異，就表示絕對差異。

示例

Input: [44, 42, 40, 23, 55]
Output: Pairs with minimum difference are:
  44 and 42
  42 and 40

說明 − 差異最小的對是 (44, 42) 和 (42, 40)。44 和 42 之間的絕對差是 2，42 和 40 之間的絕對差也是 2。

Input: [500, 200, 400, 300, 100]
Output: Pairs with minimum difference:
  100 and 200
  200 and 300
  300 and 400
  400 and 500

說明 − 在這種情況下，所有對的差都相同，為 100，因此列印所有對。

Input: [-13, 23, 79, -71, 37]
Output: Pairs with minimum difference: 
  23 and 37

說明 − 差異最小的對是 (23, 37)。23 和 37 之間的絕對差是 14，這是此列表中的最小絕對差。

樸素方法

解決這個問題的蠻力方法是比較列表中的每一對元素並計算它們的絕對差。

這種方法包括以下步驟：

• 讀取輸入整數列表

• 將 min_diff 設定為 INT_MAX

• 建立兩個變數 min_i 和 min_j，用於儲存差異最小的對的索引

• 遍歷列表，將每個元素與其他每個元素進行比較

• 如果兩個元素之間的絕對差小於 min_diff，則更新 min_diff 並將兩個元素的索引儲存在 min_i 和 min_j 中

• 如果絕對差等於 min_diff，則將索引附加到對列表中

• 完成迴圈後，列印具有最小絕對差的對

示例：C++ 程式

C++ 程式從不同的無序整數列表中查詢絕對差最小的數字對。

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>

using namespace std;
int main() {
   vector<int> nums = {4, 5, 1, 7};
   int min_diff = INT_MAX;
   int n = nums.size();
   vector<pair<int, int>> p;
   for (int i = 0; i < n-1; i++) {
      int diff = 0;
      for (int j = i+1; j < n; j++) {
         diff = abs(nums[i] - nums[j]);
         if (diff < min_diff) {
            min_diff = diff;
            p.clear();
            p.push_back(make_pair(i, j));
         }
         else if (diff == min_diff) {
            p.push_back(make_pair(i, j));
         }
      }
   }
   
   // print the answer
   for (auto x : p) {
      cout << nums[x.first] << ", " << nums[x.second] << endl;
   }
   return 0;
}

輸出

4, 5

時間和空間複雜度分析

時間複雜度：O(n²)

給定程式碼的時間複雜度為 O(n^2)。這是因為我們使用兩個巢狀迴圈來比較列表中的每個元素與其他每個元素。外迴圈執行 (n-1) 次，內迴圈執行 (n - i – 1) 次，其中 n 是列表的大小。這導致總共 (n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2 次比較，即 O(n^2) 時間複雜度。

空間複雜度：O(k)

給定程式碼的空間複雜度為 O(k)，其中 k 是具有最小絕對差的對的數量。這是因為我們將對的索引儲存在一個對向量中。在最壞的情況下，所有對都具有相同的最小絕對差，k 可以大到 n(n-1)/2，這也是 n 個元素列表中可能的最大對數。因此，程式的空間複雜度為 O(n^2)。

最佳化方法

為了最佳化解決方案，我們可以先對列表進行排序，這將花費 O(nlog(n)) 時間，然後比較相鄰元素以找到最小絕對差。

這種方法包括以下步驟：

• 按升序對整數列表進行排序。

• 初始化兩個變數 'min_diff' 和 'pairs'，分別用於儲存最小絕對差和具有相同最小絕對差的對。

• 遍歷排序後的列表並比較相鄰元素以找到最小絕對差。

• 如果找到較小的絕對差，則更新 'min_abs_diff' 並清除 'pairs' 列表並將當前對新增到其中。

• 如果找到相同的絕對差，則將當前對新增到 'pairs' 列表。

• 最後，輸出 'pairs' 列表。

示例：C++ 程式

此程式程式碼使用內建的 sort() 函式對輸入列表進行排序。然後計算每個相鄰整數對之間的差以找到答案。

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;
int main(){
   vector<int> nums = {12, 3, 19, 15, 6, 8, 1};
   sort(nums.begin(), nums.end());
   int minDiff = INT_MAX;
   vector<pair<int, int>> p;
   
   // iterate through the list and find the minimum absolute difference and pairs
   for (int i = 1; i < nums.size(); i++) {
      int diff = abs(nums[i] - nums[i - 1]);
      if (diff < minDiff) {
         minDiff = diff;
         p.clear();
         p.push_back(make_pair(nums[i - 1], nums[i]));
      }
      else if (diff == minDiff) {
         p.push_back(make_pair(nums[i - 1], nums[i]));
      }
   }
   
   // print the answer
   for (auto x : p)    {
      cout << x.first << ", " << x.second << endl;
   }
   cout << endl;
   return 0;
}

輸出

1, 3
6, 8

時間和空間複雜度分析

時間複雜度：O(nlog(n))

此程式碼的時間複雜度為 O(nlog(n))，其中 n 是輸入列表中整數的數量。這是因為程式碼首先對輸入列表進行排序，這需要 O(nlog(n)) 時間，然後遍歷排序後的列表以查詢具有最小絕對差的對，這需要 O(n) 時間。由於 O(nlog(n)) 大於 O(n)，因此整體時間複雜度為 O(nlog(n))。

空間複雜度：O(k)

此程式碼的空間複雜度為 O(k)，其中 k 是具有最小絕對差的對的數量。這是因為程式碼使用向量來儲存具有最小絕對差的對，並且此向量的最大大小為 k。

結論

給定的問題陳述是從不同的無序整數列表中找到具有最小絕對差的元素對。本文討論了問題陳述，提供了多個輸入和預期輸出場景的示例，並提供了一種蠻力解決方案和一種有效的解決方案方法來解決此問題。本文還包括所使用的演算法以及用於實現解決方案方法的 C++ 程式。最後，本文還詳細討論瞭解決方案的時間和空間複雜度。