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

在本文中，我们将讨论如何在 C++ 中查找未排序整数列表中的最接近的数字。

问题陈述

从一系列未排序的整数列表中，我们需要找到相互之间差异最小的整数对。如果存在多个对，我们需要找到每一个。此外，在本文中，“差值”一词始终指绝对差值。

示例

解释：对 (44, 42) 和 (42, 40) 的差值最小。四十与四十二之间，以及四十与四十四之间，绝对差值均为二。

解释 - 在这种情况下，所有对的差值都相同，为 100，因此打印所有对。

朴素方法

要以蛮力方式解决此问题，请比较列表中的每一对元素，并计算它们之间的绝对差值。

该方法包括以下步骤：

• 检查整数输入列表。
• 将 INT_MAX 设置为 min_diff。
• 创建变量 min_i 和 min_j 来保存具有最小差值的对的索引。
• 在我们遍历列表时，将每个条目与每个其他条目进行比较。
• 如果两个元素之间的绝对差值小于 min_diff，则更新 min_diff 并将这两个元素的索引保存在 min_i 和 min_j 中。
• 如果绝对差值等于 min_diff，则将索引添加到对列表中。

示例

让我们举一个例子，在 C++ 中从未排序的整数列表中查找最接近的数字。

输出

说明

• nums：一个整数向量。
• min_diff：存储已找到的最小差值的变量，初始化为可能的最大整数值。
• n：向量 nums 的大小。
• p：一个向量，用于存储具有最小差值的索引对。
• 外循环从第一个元素到倒数第二个元素开始。
• 在内循环中，将出现的每个元素 i 与其后的所有元素 j 进行比较。
• diff 确定索引 i 和 j 处的元素之间的绝对差值。
• 如果 diff 小于当前的 min_diff，则更新 min_diff 并清空向量 p 以保存新对。
• 如果 diff 等于 min_diff，则将新对添加到 p。
• 当您遍历向量 p 时，打印 nums 中具有最小差值的数字对。

时间和空间复杂度分析

时间复杂度： O(n2)

其时间复杂度为 O(n^2)。这是因为使用了两个嵌套循环来将列表的每个元素与每个其他元素进行比较。外部循环运行 (n-1) 次，内部循环运行 (n - i - 1) 次，其中 n 是列表的大小。由于其 O(n^2) 的时间复杂度，总共有 (n - 1) + (n - 2) +... + 1 = n(n - 1) / 2 次比较。

空间复杂度： O(k)

它具有 O(k) 的空间复杂度，其中 k 是具有最小绝对差值的对的数量。这是因为我们在一个对向量中存储了对索引，该向量的最大大小为 k，这对应于 n 个条目的列表中可能存在的最大配对数，即 n(n-1)/2。因此，该程序的空间复杂度为 O(n^2)。

优化方法

通过对列表进行排序，我们可以比较相邻的条目来找到最小的绝对差值。但是，优化该方法将需要 O(log (n)) 的时间。该方法包括以下步骤：

• 在列表中，整数按升序排列。
• 为变量“min_diff”和“pairs”设置初始值，以便可以存储最小绝对差值以及共享它的对。
• 遍历排序列表并比较相邻的元素，以找到具有最小绝对差值的元素。
• 如果找到较小的绝对差值，则更新“min_abs_diff”，清空“pairs”列表，并将当前对添加到其中。
• 如果找到相同的绝对差值，则应将当前对添加到“pairs”列表中。
• 最后一步是打印“pairs”列表。

示例

让我们再举一个例子，在 C++ 中从未排序的整数列表中查找最接近的数字。

输出

说明

• nums 向量按升序排序。排序需要 O(nlogn) 时间。
• 接下来，将 minDiff 的初始值设置为可以找到的最大整数。
• 继续遍历排序后的向量，从第二个元素开始。
• 确定每个元素与其前一个元素之间的确切差值。
• 如果差值小于当前的 minDiff，则更新 minDiff，清空 pairings 向量 p，并添加新对。
• 如果差值等于当前的 minDiff，则将新对添加到 p。
• 当您遍历向量 p 时，打印具有最小差值的每个值对。

时间和空间复杂度分析

时间复杂度： 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。