题目链接

算法竞赛进阶指南-50.邻值查找

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

对于 $A$ 中的每一个数 $A_i$，求：

$\min_{1 \le 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 \le j <i}|A_i-A_j|$ 和 $ P_i $ 的值。

数据范围

$n \le 10^5 $,$ |A_i| \le 10^9$

输入样例：

3
1 5 3

输出样例：

4 1
2 1

Method1 : STL-set

这题的意思就是在$A_i$前面找一个与$A_i$数值最接近的一个数$A_j$，如果有两个数同时满足，选择$A_j < A_i$的那个。

看到题目数据范围$1*10^5$就知道不能用暴力写，要找一个$O(nlogn)$的做法。

复杂度分析

• 时间复杂度：${O(n \log n)}$， 其中$\log n$为对n进行二进制拆分的时间复杂度。
• 空间复杂度：${O(1)}$。

Method2 : 双向链表

用链表就是离线做法：

将原数组带着下标一起，按照元素的值从小到大顺排，然后以此顺序建立双向链表，而且要从后往前考虑

#include <iostream>
#include <algorithm>
#include <limits.h>

using namespace std;

typedef pair<int, int> PII;

struct Node {
    int value;
    int pos;
    int nxt, pre;
    bool operator< (const Node& rhs) const {
        return value < rhs.value;
    }
};

const int N = 1e5 + 7;

int n;
Node node[N];
int head, tail, tot;

void init() {
    tot = 2;
    head = 1, tail = 2;
    node[head].nxt = tail;
    node[tail].pre = head;
}

int insert(int p, int v, int idx) {
    int q = ++ tot;
    node[q].value = v;
    node[q].pos = idx;
    node[node[p].nxt].pre = q;
    node[q].nxt = node[p].nxt;
    node[p].nxt = q; node[q].pre = p;
    return q;
}

void remove(int p) {
    node[node[p].pre].nxt = node[p].nxt;
    node[node[p].nxt].pre = node[p].pre;
}

int pos[N];
PII res[N], a[N];

int main() {
    init();
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++) {
        scanf("%d", &a[i].first);
        a[i].second = i;
    }
    
    sort(a + 1, a + 1 + n);
    
    for (int i = 1; i <= n; i ++) {
        pos[a[i].second] = insert(node[tail].pre, a[i].first, a[i].second);
    }
    
    for (int i = n; i > 1; i --) {
        int s = INT_MAX, idx = -1;
        Node& t = node[pos[i]];
        if (t.pre != head && s > abs(t.value - node[t.pre].value)) {
            s = abs(t.value - node[t.pre].value);
            idx = node[t.pre].pos;
        }
        if (t.nxt != tail && s > abs(t.value - node[t.nxt].value)) {
            s = abs(t.value - node[t.nxt].value);
            idx = node[t.nxt].pos;
        }
        res[i] = {s, idx};
        remove(pos[i]);
    }
    
    for (int i = 2; i <= n; i ++) {
        printf("%d %d\n", res[i].first, res[i].second);
    }
    
    return 0;
}

复杂度分析

• 时间复杂度：${O(n \log n)}$， 其中$n\log n$为sort的时间复杂度。
• 空间复杂度：${O(1)}$。

补一个暴力做法，会$TLE$。

#include <iostream>
#include <algorithm>
#include <limits.h>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e5 + 7;

int n;
vector<int> arr(N);

int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        scanf("%d", &arr[i]);
    }
    
    vector<PII> res;
    for (int i = 2; i <= n; i ++) {
        PII tmp;
        tmp.first = INT_MAX;
        tmp.second = i;
        for (int j = i - 1; j; j --) {
            int dif = abs(arr[i] - arr[j]);
            if (dif < tmp.first) {
                tmp.first = dif;
                tmp.second = j;
            }
            else if (dif == tmp.first) {
                if (arr[j] < arr[i]) tmp.second = j;
            }
        }
        
        res.push_back(tmp);
    }
    
    for (int i = 0; i < res.size(); i ++) {
        printf("%d %d\n", res[i].first, res[i].second);
    }
    
    return 0;
}