从无序整数列表中查找最接近的数字

---

在下面的文章中，我们将讨论两种从无序整数列表中查找最接近数字的方法。让我们首先了解“最接近数字”的含义。“最接近数字”是指差异最小的数字对。

问题陈述

给定一个不同的无序整数列表，我们需要找到差异最小的元素对。如果有多个对，我们需要找到所有对。此外，在本文中，只要提到差异，就表示绝对差异。

示例

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++ 程序。最后，本文还详细讨论了解决方案的时间和空间复杂度。