邻值查找

题目

题目描述

给定一个长度为 nn 的序列 A，A 中的数各不相同。对于 A 中的每一个数 Ai，求：

min(1≤j<i) |Ai−Aj|min(1≤j<i) ⁡|Ai−Aj|

以及令上式取到最小值的 j（记为 Pi）。若最小值点不唯一，则选择使 Aj较小的那个j。

---

输入

第一行一个整数 n，第二行 n 个数 A1至An。

输出

n−1 行，每行 2 个用空格隔开的整数。分别表示当 i∈[2,n]时，对应的 min(1≤j<i) |Ai−Aj| 和 Pi 的值。

---

样例输入

3
1 5 3

样例输出

4 1
2 1

---

数据规模与约定

时间限制：1 s

内存限制：256 M

100% 的数据保证 n≤105, Ai <= 1e9

思路

• 首先读懂题目

• 排序：升序

• 从原始数列最后一个元素开始查找，查找完成把该元素剔除

题解 1:利用数组做的

自己写的3000ms左右

#include 
#include 
#include 
#include 
using namespace std;

typedef pair  PA;
typedef long long ll;

PA nums[100005];
PA da[100005]; //da[i].first = min|Ai - Aj|, da[i].second = Pj; i > j >= 1; 保存答案，方便输出； 
int key[100005];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &nums[i].first);
        nums[i].second = i;
    }
    sort(nums + 1, nums + n + 1);
//    for (int i = 1; i <= n; i++) {
//        cout << nums[i].first << ' ' << nums[i].second << endl;
//    }
    for (int i = 1; i <= n; i++) {
        key[nums[i].second] = i; //排序后数列位置 <= 数列原位置 
    }
    int min = 1e9 + 10;
    int max = -1e9 - 10;
    nums[0] = {min, 0};
    nums[n + 1] = {max, n + 1};
    for (int i = n; i >= 2; i--) { //i指向原数列元素的位置 
        int key_i = key[i]; //key_i指向排序后元素位置；找到原数列元素在排序后数列的位置
        int i_y = key_i + 1; //指向排序后key_i右边的元素
        while (i_y < n + 1 && nums[i_y].first == max) i_y++;
        int i_z = key_i - 1; //指向排序后key_i左边的元素 
        while (i_z && nums[i_z].first == max) i_z--;
        ll abs1 = abs(nums[i_z].first - nums[key_i].first); //右边数 
        ll abs2 = abs(nums[i_y].first - nums[key_i].first); //左边数
        if (abs1 > abs2) {
            da[i].first = abs2, da[i].second = nums[i_y].second;
        } else {
            da[i].first = abs1, da[i].second = nums[i_z].second;
        }
        nums[key_i].first = max;
    }
    for (int i = 2; i <= n; i++) printf("%d %d\n", da[i].first, da[i].second);
    return 0;
}

题解 2：自己写的双向链表

自己用C写的2000ms左右

思路

• 主要处理边界问题

#include 
#include 
#include 

typedef struct root {
    int key;
    int val;
} root;

//结构定义
typedef struct Node { //节点定义 
    root *val;
    struct Node *next; // 后驱指针 -> 
    struct Node *per;  //前驱指针 <-
} Node;

typedef struct DList {
    Node head;
} DList;

DList *init_DList() { //链表初始化 
    DList *l = (DList *)malloc(sizeof(DList));
    l->head.next = NULL;
    return l;
}

Node *getNewNode(root *val) { //节点初始化
    if (val == NULL) return NULL;
    Node *n = (Node *)malloc(sizeof(Node));
    n->val = val;
    n->next = n->per = NULL;
    return n;
}

void insert(DList *l, root *val) { // 头插法 节点插入
    if (l == NULL) return ;
    Node *p = &(l->head), *n = getNewNode(val);
    n->next = p->next;
    l->head.next = n;
    if (n->next) n->next->per = n;
    return ;
}

void delete_Node(DList *l, Node *n) { //节点删除
    if (n == NULL) return ;
    Node *p = n->next, *q = n->per;
    if (p == NULL) {
        q->next = NULL;
    } else if (q == NULL) {
        l->head.next = p;
        p->per = NULL;
    } else {
        p->per = q;
        q->next = p;
    }
    free(n);
    return ;
}

root nums[100005];
root da[100005];

void quick_sort(root *num, int l, int r) {//结构体快速排序 
    //数据越乱越好 
    if (l > r) return ;
    int x = l, y = r;
    root z = num[x];
    while (x < y) {
        while (x < y && num[y].val > z.val) y--;
        if (x < y) num[x++] = num[y];
        while (x < y && num[x].val < z.val) x++;
        if (x < y) num[y--] = num[x];
    }
    num[x] = z;
    quick_sort(num, l, x - 1);
    quick_sort(num, x + 1, r);
    return ;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &nums[i].val);
        nums[i].key = i;
    }
    quick_sort(nums, 1, n);
//    for (int i = 1; i <= n; i++) {
//        cout << nums[i].val << ' ' << nums[i].key << endl;
//    }
    DList *l = init_DList();
    for (int i = n; i >= 1; i--) {
        //vis[nums[i].key] = i;
        insert(l, &nums[i]);
    }
    Node *q = l->head.next; // 保存上一个位置
    for (int i = n; i >= 2; i--) {
        Node *p = q;
        int pos = i;
        while (p->val->key != pos && p->next) p = p->next;
        if (pos != p->val->key) {
            p = q;
            while (p->val->key != pos && p->per) p = p->per;
        }
        int data = p->val->val;
        int abs1 = 2e9 + 10, abs2 = 2e9 + 10;
        if (p->next) {
            int qian = p->next->val->val;
            q = p->next;
            abs1 = abs(qian - data);
        }
        
        if (p->per) {
            int hou= p->per->val->val;
            q = p->per;
            abs2 = abs(hou - data);
        }
        
        if (abs1 >= abs2) {
            da[i].val = abs2;
            da[i].key = p->per->val->key;
        } else {
            da[i].val = abs1, da[i].key = p->next->val->key;
        } 
        delete_Node(l, p);
    }
//    for (int i = 2; i <= n; i++) {
//        cout << da[i].first << ' ' << da[i].second << endl;
//    }
    for (int i = 2; i <= n; i++) printf("%d %d\n", da[i].val, da[i].key);
    free(l); 
    return 0;
}

题解3：利用数组实现双向链表

看了视频后自己写的，120ms左右

#include 
#include 
#include 

using namespace std;

#define N 100005 

typedef pair PII;

PII nums[N], ans[N];
int r[N], l[N], vis[N];
// 数组vis用来查找原始数列在排序后数列的位置
// 数组r为双向链表的右指针，l为左指针 




int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &nums[i].first);
        nums[i].second = i;
    }
    sort(nums + 1, nums + 1 + n);
    for (int i = 1; i <= n; i++) {
        vis[nums[i].second] = i; //查找原始数列在排序后数列的位置
        r[i] = i + 1, l[i] = i - 1; //链接链表
    }
    
    //边界处理 
    nums[0] = {1e9 + 10, 0};
    nums[n + 1] = {-(1e9 + 10), n + 1};
     
    for (int i = n; i > 1; i--) { //从n开始保证是最大的 
        int pos = vis[i]; 
        int right = r[pos], left = l[pos];
        int abs_r = abs(nums[pos].first - nums[right].first);
        int abs_l = abs(nums[pos].first - nums[left].first);
        if (abs_l <= abs_r) {
            ans[i].first = abs_l, ans[i].second = nums[left].second;
        } else {
            ans[i].first = abs_r, ans[i].second = nums[right].second;
        }
        
        //删除节点
        r[left] = right, l[right] = left;
    }
    for (int i = 2; i <= n; i++) printf("%d %d\n", ans[i].first, ans[i].second);
    return 0;
}

用了快读与快写，直接跑到112ms

#include 
#include 
#include 

using namespace std;

#define N 100005 

typedef pair PII;

PII nums[N], ans[N];
int r[N], l[N], vis[N];
// 数组vis用来查找原始数列在排序后数列的位置
// 数组r为双向链表的右指针，l为左指针 


inline int read() {
    int x = 0, w = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        w |= ch == '-';
        ch = getchar();
    } 
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return w ? -x : x;
}


inline void write(int x) { //快写 
    
    char f[200];
    
    if (!x) {
        putchar('0');
        return ;
    }
    int tmp = x > 0 ? x : -x;
    int cnt = 0;
    (x < 0) && putchar('-');
    while (tmp > 0) {
        f[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0) {
        putchar(f[--cnt]);
    }
} 
int main() {
    int n;
    n = read();
    for (int i = 1; i <= n; i++) {
        nums[i].first = read();
        nums[i].second = i;
    }
    sort(nums + 1, nums + 1 + n);
    for (int i = 1; i <= n; i++) {
        vis[nums[i].second] = i; //查找原始数列在排序后数列的位置
        r[i] = i + 1, l[i] = i - 1;
    }
    
    //边界处理 
    nums[0] = {1e9 + 10, 0};
    nums[n + 1] = {-(1e9 + 10), n + 1};
     
    for (int i = n; i > 1; i--) { //从n开始保证是最大的 
        int pos = vis[i]; 
        int right = r[pos], left = l[pos];
        int abs_r = abs(nums[pos].first - nums[right].first);
        int abs_l = abs(nums[pos].first - nums[left].first);
        if (abs_l <= abs_r) {
            ans[i].first = abs_l, ans[i].second = nums[left].second;
        } else {
            ans[i].first = abs_r, ans[i].second = nums[right].second;
        }
        //删除节点
        r[left] = right, l[right] = left;
    }
    
    
    for (int i = 2; i <= n; i++) 
        write(ans[i].first), putchar(' '), write(ans[i].second), putchar('\n');
    return 0;
}

总结

• 通过这道题学习到了双向链表利用数组实现的方法

• 利用两个方向数组实现了链表的双向功能，和删除节点的功能

• 利用数组实现的双向链表查找和删除时间复杂度多少O(1)，远远比利用结构体快得多，结构体查找时间复杂度为O(n)，删除功能为O(1);