每周一算法：邻值查找

本文主要是介绍每周一算法：邻值查找，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给定一个长度为 $n$ 的序列 $A$ ， $A$ 中的数各不相同。

对于 $A$ 中的每一个数 $A_i$ ，求： $min_{1≤j<i}|A_i−A_j|$ ，以及令上式取到最小值的 $j$ （记为 $P_i$ ）。若最小值点不唯一，则选择使 $A_j$ 较小的那个。

输入格式

第一行输入整数 $n$ ，代表序列长度。

第二行输入 $n$ 个整数 $A_1…A_n$ ，代表序列的具体数值，数值之间用空格隔开。

输出格式

输出共 $n - 1$ 行，每行输出两个整数，数值之间用空格隔开。

分别表示当 $i$ 取 $2\sim n$ 时，对应的 $min_{1≤j<i}|A_i−A_j|$ 和 $P_i$ 的值。

数据范围

$n\le10^5$ ， $A_i|≤10^9$

输入样例

3
1 5 3

输出样例

4 1
2 1

算法思想一

根据题目描述，对于每个元素 $A_i$ ，要找到其左边与它差值最小的元素 $A_j$ （ $1\le j \lt i$ ），输出它们的差值的绝对值 $A_i-A_j|$ ，以及 $j$ 。

计算与 $A_i$ 差值有两种情况：

$A_i<A_j$ ，差值 $v = A_j-A_i$
$A_i>A_j$ ，差值 $v = A_i-A_j$

也就是说，对于任意的 $A_i$ ，如果能在 $1\sim i$ 之间找到与 $A_i$ 大小相邻的两个数 $A_l$ 和 $A_r$ ，其中 $A_l$ 是小于 $A_i$ 的最大值， $A_r$ 是大于 $A_i$ 的最小值，分别计算其与 $A_i$ 的差值，取其中的较小者即可。

从给出的数据范围来看， $n\le10^5$ ，对于每个元素必须在 $O (l o g n)$ 的时间复杂度内，查找到大小相邻的两个元素，而且根据题目中给出的限制，序列 $A$ 的数各不相同，可以用C++ 标准库的std::set 来实现。

std::set 是 C++ 标准库中的一个容器，它按有序方式存储唯一元素的集合。std::set 中的元素自动按照严格弱序（Strict Weak Ordering）排序，并且每个元素都是唯一的。这意味着 std::set 中的元素是按照特定顺序排列并且不会存在重复值。下面是一些 std::set 的特点和用途：

自动排序：std::set 内部使用红黑树（一种自平衡的二叉搜索树）实现，因此元素在容器中按照严格弱序排序。这使得元素能够以有序的方式存储，方便进行遍历和搜索操作。
唯一性：std::set 中的元素是唯一的，相同的元素只会在容器中存在一个副本。这可以确保每个元素在集合中的唯一性。
插入和查找效率高：由于 std::set 内部使用红黑树实现，插入和查找元素的时间复杂度为 $O (l o g n)$ ，其中 $n$ 是容器中的元素数目。这使得 std::set 适合于需要高效地插入和查找元素的情况。
std::set的大部分操作是与vector类似的，不过set不支持随机访问，必须要使用迭代器去访问；
std::set插入元素的方法为insert
std::set查找元素的方法为find，返回一个迭代器set<类型>::iterator
若元素存在，返回的迭代器指向键值
若元素不存在，返回的迭代器指向set.end()。

由于set是以有序方式存储唯一元素，那么可以遍历每个元素 $A_i$ ：

将 $A_i$ 插入到set中
在set中查找元素 $A_i$ ，返回指向 $A_i$ 的迭代器
通过迭代器可以找到与 $A_i$ 大小相邻的两个元素，打擂台求最小值即可

时间复杂度

遍历每个元素 $A_i$ ，时间复杂度为 $O (n)$
在set中查找 $A_i$ ，时间复杂度为 $O (l o g n)$

总的时间复杂度为 $O (n l o g n)$

代码实现

#include <iostream>
#include <set>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> PII;
int main()
{int n, x;cin >> n;set<PII> st;for(int i = 1; i <= n; i ++){cin >> x;PII a = {x, i};st.insert(a);if(i > 1) {auto it = st.find(a); //find返回迭代器：set<pair<int, int>>::iteratorint k = INF, p;if(++ it != st.end()) //通过迭代器找到下一个元素k = (*it).first - x, p = (*it).second;-- it; //将迭代器回到之前位置if(it != st.begin() && x - (*--it).first <= k) //如果和前一个元素的差值不大于kk = abs((*it).first - x), p = (*it).second;cout << k << " " << p << endl;}}
}

算法思想二

除了使用 std::set实现，这里再介绍一个双链表的实现方法。

首先将序列 $A$ 排序，假设排序后为 $A_3A_4...A_n...A_2$
根据上述序列可以构造出一个双链表，如下图所示

在这里插入图片描述
有了双链表之后，如何求 $A_i$ 左边与它差值最小的元素呢？可以从后向前处理，也就是从 $A_n$ 开始，因为 $A_n$ 是原序列中最后一个元素，因此其它元素都在它左边。那么：

对于元素 $A_n$ 来说，假设其在双链表的位置为 $k$ ，其左边的元素 $L [k]$ 就是小于 $A_n$ 的最大值，其右边元素 $R [k]$ 就是大于 $A_n$ 的最小值。
计算完相邻元素的差值之后，将 $A_n$ 从双链表中删除，继续处理前一个元素。

重复这个过程，直到所有元素都处理完。

时间复杂度

排序的时间复杂度为 $O (n l o g n)$
排序后构建双链表的时间复杂度为 $O (n)$
查找计算相邻元素差值的时间复杂度为 $O (n)$

总的时间复杂度为 $O (n l o g n + n + n)$

代码实现

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
typedef pair<LL, int> PII;
PII a[N], ans[N];
int p[N], L[N], R[N];
int main()
{int n, x;cin >> n;for(int i = 1; i <= n; i ++){cin >> x;a[i] = {x, i};}sort(a + 1, a + n + 1);//设置链表的首尾的值，避免其差值被选上a[0].first = -1e10, a[n + 1].first = 1e10; for(int i = 1; i <= n; i ++){p[a[i].second] = i; //统计每个元素的新位置L[i] = i - 1, R[i] = i + 1; //建立双链表}//从第n个元素开始处理for(int i = n; i > 1; i --){//第i个元素所在位置kint k = p[i], left = L[k], right = R[k], v = a[k].first;LL lv = v - a[left].first; //与左边对应元素的差值LL rv = a[right].first - v; //与右边对应元素的差值if(lv <= rv) ans[i] = {lv, a[left].second};else ans[i] = {rv, a[right].second}; L[right] = left, R[left] = right; //删除k结点}//输出结果for(int i = 2; i <= n; i ++)cout << ans[i].first << " " << ans[i].second << endl;
}