加索引的数组

摘要: 加索引的数组

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

$0 背景

有些数据结构可以根据 key 快速找到其所在节点，例如哈希表、平衡树、Trie，跳表。这些可以看成是一种自带索引的数据结构(索引结构)。即将数据项(key)插入进去之后，可以随时根据给定的 key，可以快速查到它所在节点的位置。

作为对比，数组，链表就没有这种根据 key 快速找到其所在节点的特性，数据项(key)插入进去之后，如果想给定 key 找到对应的节点，只能线性扫描去找。(栈，队列，堆这三种数据结构，节点的组织方式依然是数组或链表，本质不变)。

对于数组或链表，如果想在插入数据之后通过 key 找到节点，可以通过借助索引结构给节点建立索引的方式实现。

$1 对数组的索引

对于链表，可以手动建一层索引，使得通过 key 可以快速定位到对应的节点。链表同时又天然地支持快速插入删除节点，于是加索引的链表就可以形成支持快速插入，删除，查找的结构。

参考：加索引的链表

对于数组，可以手动建一层索引，使得通过 key 可以快速定位到对应的节点。这一点是没问题的。例如 key -> idx 表示 key 对应节点为数组下标 idx，实现快速的查到 key 所在节点的需求。

但是数组存 key 的情况，通过这样的方式得到节点 idx 之后，并不好做删除节点 idx 以及在 idx 两侧插入节点的操作，如果同时有通过 key 找到节点 idx 以及在 idx 位置插入删除节点的需求，不如直接用加索引的链表。

找到对应节点(数组下标)之后，虽然不能直接删除节点或者在两侧插入节点，或者调度节点，但是可以通过交换到尾部的方式实现插入删除。

• 如果想删除，不能直接删除，因为 $O(N)$，需要将该节点交换到尾部，在从尾部删除
• 插入的话，无法在该节点的相邻位置直接插入，因为 $O(N)$，需要先插入到尾部，再交换到该位置

维护索引需要注意除了当节点被删除后索引也要删之外，节点被算法调度到别的位置了，索引也要更新，因为数组的索引结果是下标而不是指针，如果不更新，索引到的下标可能是其它元素或者已经越界了，这点与链表的索引不太一样。

---

建立索引时候，用于建立索引的字段(key)，以及使用的索引结构需要根据需求设计。

---

(0) 随机索引

数组的最大的特性就是可以通过下标直接访问，而产生当前数组中节点的合法下标并不需要有 key 才可以，例如可以通过随机数的方式获得。通过这种方式可以实现支持插入元素，弹出随机元素的随机队列。

随机索引没有建索引的过程，只需要知道存数据的数组的长度。

• 随机队列

---

(1) 线性索引

将数组中数据的 key 和数据在数组中的节点位置以元组的形式放进数组维护，这个保存 key 和节点位置的数组称为线性索引表。

• 线性索引表

---

(2) 哈希索引

将数组中数据的 key 作为哈希表的键，将数据在数组中的节点位置作为值放进哈希映射维护。

当数据通过与尾部交换的方式插入删除时，数据在数组中的节点位置发生变化，需要更新索引，由于在哈希表中查 key 是 $O(1)$ 的，更新索引比较方便。

例如在索引堆中，内部维护了一个哈希索引，通过 key 可以查询到持有这个 key 的下标集合，存数据的数组在插入删除以及维护堆的性质时对数组的修改会同步到哈希索引。

• 索引堆1

---

(3) 树形索引

将数组中的 key 作为平衡树的键，key 在数组中的节点下标作为值维护在平衡树里。

当数据通过与尾部交换的方式插入删除时，数据在数组中的节点位置发生变化，需要更新索引，由于在平衡树中查 key 是 $O(\log N)$ 的，比哈希索引弱，但是可以维护 key 的某种顺序。

136. 邻值查找

给定一个长度为 n 的序列 A，A 中的数各不相同。对于 A 中的每一个数 $A_{i}$，求：

$$\min\limits_{1\leq j < i}|A_{i}−A_{j}|$$

以及令上式取到最小值的 j（记为 $P_{i}$）。若最小值点不唯一，则选择使 $A_{j}$ 较小的那个。

算法1: 对数组做树形索引

数据保存在数组里，并且数组保持不变，用平衡树对数组做索引，通过 key 可以得到该数据的下标。mapping[A[i]] = i

map<int, int> mapping;

代码 (C++)

int main()
{
    int n;
    cin >> n;
    vector<int> A(n);
    map<int, int> mapping;
    for(int i = 0; i < n; ++i)
    {
        cin >> A[i];
        mapping[A[i]] = i;
        if(i == 0) continue;
        // 2 < i < n
        // 1 <= j < i
        // 比 A[i] 大的最小的数 x1, 下标 p1
        // 比 A[i] 小的最大的数 x2, 下标 p2
        int x = -1, p = -1;
        auto it1 = mapping.upper_bound(A[i]);
        if(it1 != mapping.end())
        {
            int x1 = it1 -> first;
            int p1 = it1 -> second;
            x = x1;
            p = p1;
        }
        auto it2 = mapping.lower_bound(A[i]);
        if(it2 != mapping.begin())
        {
            --it2;
            int x2 = it2 -> first;
            int p2 = it2 -> second;
            if(p == -1 || x - A[i] >= A[i] - x2)
            {
                x = x2;
                p = p2;
            }
        }
        cout << abs(A[i] - x) << " " << p + 1 << endl;
    }
}

算法2: 索引链表

将 A 排序，然后串成链表。

sort(A.begin(), A.end());
list l(A.begin(), A.end());

此时对于 l 中的元素 it, it -> next 和 it -> prev 就是 it 的前驱和后继。

从 A[n-1] 开始处理，一直处理到 A[0]，处理完后将对应在链表中的元素删掉。

l 排序之后，我还需要原始下标 idx 对应到排序后的链表 l 中的哪个节点，对 l 建立索引，实现方式是 vector<list<int>::iterator> indexes，it = indexes[i] 表示排序前的数组节点 A[i] 在排序后的链表中对应的节点。

it 相邻的元素就是其前驱后继，输出答案是需要带上前驱或后继的原始下标，方案为在 l 的节点中加一个原始下标的字段，由于 l 是在排序 A 的基础上建立的，因此在排序 A 的时候就要带着原始下标的字段。

代码 (C++)

#include <iostream>
#include <vector>
#include <cmath>
#include <list>
#include <algorithm>

using namespace std;

struct Item
{
    int val;
    int idx; // 反向索引
    Item(int v, int i):val(v),idx(i){}
};

struct Cmp
{
    bool operator()(const Item& i1, const Item& i2) const
    {
        return i1.val < i2.val;
    }
};

int main()
{
    int n;
    cin >> n;
    vector<Item> A;
    for(int i = 0; i < n; ++i)
    {
        int v;
        cin >> v;
        A.emplace_back(v, i);
    }
    sort(A.begin(), A.end(), Cmp());
    vector<list<Item>::iterator> indexes(n);
    // indexes[i] := 原始位置为 i 的元素 A[i] 在链表中对应的元素
    list<Item> l;
    for(int i = n - 1; i >= 0; --i)
    {
        l.push_front(A[i]);
        indexes[A[i].idx] = l.begin();
    }
    vector<Item> result;
    for(int i = n - 1; i >= 1; --i)
    {
        auto it = indexes[i];
        if(it == l.end()) continue;
        int a = it -> val;
        int x = -1, p = -1;
        if(it != l.begin())
        {
            --it;
            int x1 = it -> val;
            int p1 = it -> idx;
            x = x1;
            p = p1;
            ++it;
        }
        ++it;
        if(it != l.end())
        {
            int x2 = it -> val;
            int p2 = it -> idx;
            if(p == -1 || x2 - a < a - x)
            {
                x = x2;
                p = p2;
            }
        }
        --it;
        result.emplace_back(abs(a - x), p + 1);
        l.erase(it);
        indexes[i] = l.end();
    }
    int m = result.size();
    for(int i = m - 1; i >= 0; --i)
        cout << result[i].val << " " << result[i].idx << endl;
}

---