算法数据结构

线性索引表

字数统计: 2.4k字   |   阅读时长: 10分
, ,

摘要: 线性索引表的原理，例子

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

$1 线性索引表

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

线性索引表

如果只是建这么一个线性索引表，其实用处不大：

  • 调度节点层面：当数据通过与尾部交换的方式插入删除时，数据在数组中的节点位置发生变化，需要更新索引，由于在数组中查找 key 是 $O(N)$ 的，更新索引比较困难。
  • 查询层面：通过线性索引查询 key，只能从头到尾遍历线性索引表，时间也是 $O(N)$，等于没做索引

线性索引表有一种比较有用的用法是静态查找表，应用在没有调度节点的需求的场景，即存数据的数组不做修改，没有增删改的操作。

(1) 静态查找表

当存数据的数组不做修改，即没有插入节点，删除节点，修改数据的操作时，将线性索引表中的(key, 节点位置)元组按 key 排序，就可以以二分的方式在 $O(\log N)$ 的时间查找 key，然后找到节点位置。这样的线性索引表就是静态查找表。

静态的意思就是存数据的数组不做修改，如果存数据的数组修改了，例如数据通过与尾部交换的方式插入删除时，数据在数组中的节点位置发生变化，需要更新索引，虽然线性索引表有序可以 $O(\log N)$ 了，但是更新索引依然是 $O(N)$ 的，因为要保持线性索引表有序就得移动节点，因此如果数据有插入删除同时还要维护 key 的顺序的话，还是得上树形索引。

代码 (C++，模板)

当数据没有插入删除的时候，并且节点持有的对象很重不能直接调度(例如交换节点持有的对象)，通过建立线性索引表然后排序的方式建立静态查找表是一种支持查询请求的不错的方式，一般的实现方式如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
struct Object
{
    int key;
    // 比较重，不方便移动的内容
};

const vector<Object> objects; // 存数据的数组

struct Item
{
    int key;
    int idx;
    Item(int k, int i):key(k),idx(i){}
};

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

vector<Item> indexes;
for(int i = 0; i < (int)objects.size(); ++i)
    indexes.emplace_back(objects[i], i);
sort(indexes.begin(), indexes.end(), Cmp());

(2) 以下标为key的静态查找表

在对 vector<Object> vec 建立线性索引表，进而排序形成静态查找表 vector<int> indexes 的过程中，key 可以直接用 vec 的下标，因为 vec 不做改变，所有 vec 的下标唯一地标识了对象，如图。

只记录数组下标的静态查找表

通过 vec[indexes[i]] 可以拿到存数据的数组中对应的节点持有的对象。在排序的时候，以 vec[indexes[i]] 为排序依据，而交换节点时，只交换 indexes 中的节点。最终 vec 不变，indexes 按照 vec[indexes[i]] 排序。如果要查询 key 的时候依然可以二分。

代码 (C++，模板)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct Object
{
    int key;
    // 比较重，不方便移动的内容
};

const vector<Object> objects; // 存数据的数组

struct Cmp
{
    vector<Object> *data;
    Cmp(vector<Object>* const nums):data(nums){}
    bool operator()(const int& i1, const int& i2) const
    {
        return data -> at(i1) < data -> at(i2);
    }
};

vector<int> indexes;
for(int i = 0; i < (int)objects.size(); ++i)
    indexes.push_back(i);
Cmp cmp(objects);
sort(indexes.begin(), indexes.end(), cmp);

代码测试

通过只记录数组下标的静态查找表实现原数组的排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> indexes(n);
        for(int i = 1; i < n; ++i)
            indexes[i] = i;
        Cmp cmp(&nums);
        sort(indexes.begin(), indexes.end(), cmp);
        vector<int> result;
        for(int i: indexes)
            result.push_back(nums[i]);
        return result;
    }

private:
    struct Cmp
    {
        vector<int> *data;
        Cmp(vector<int>* const nums):data(nums){}
        bool operator()(const int& i1, const int& i2) const
        {
            return data -> at(i1) < data -> at(i2);
        }
    };
};

$2 315. 计算右侧小于当前元素的个数

给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

提示：

1
2
1 <= nums.length <= 1e5
-1e4 <= nums[i] <= 1e4

示例 1：
输入：nums = [5,2,6,1]
输出：[2,1,1,0]
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素

示例 2：
输入：nums = [-1]
输出：[0]

示例 3：
输入：nums = [-1,-1]
输出：[0,0]

算法: 线性索引表 + CDQ 分治

本题可以用类似于在归并排序的归并阶段统计信息的过程，这是一种基于时间的离线分治算法(CDQ)，可以参考文章 离线分治：基于时间 (CDQ分治)，在 493. 翻转对 中也用的这个算法，参考文章 权值线段树、权值树状数组。

但是本题有所不同：归并阶段统计信息时要追溯元素在原始数组中的位置。正常的归并排序过程中，元素的位置已经被打乱，此时要追溯元素在原数组的位置，需要引入索引数组的思想。

考察归并排序过程中的其中一次归并，现在两个子数组 p[left .. mid], q[mid + 1 .. right] 已经有序，现在正在归并。当 p 前进到 i 位置，q 前进到 j 位置时，p[left .. i - 1], q[mid + 1, .. j - 1] 都已经进入了归并排序的辅助数组。此时若 p[i] <= q[j], p[i] 准备进入辅助数组，在进入之前，问：此时 q 中已经有多少个数字进入了辅助数组，答案是 j - mid。这个是本轮归并对 p[i] 这个数的答案的贡献，因为这些是在 p[i] 的右边且小于 p[i] 的。把历次归并对该数的贡献相加，就得到 p[i] 对应的答案。

线性索引表

j - mid 这个贡献要追加到 p[i] 在原数组中的位置上，假设 p[i] 在原数组中的位置是 idx, 则更新贡献值的操作是 result[idx] += j - mid; 但是在归并排序过程中，p[i] 在原数组中的位置已经改变，此时要获取 p[i] 在原数组中的位置 idx，有两种方案。

这种索引数组的思想可以理解为：元素在算法的流程中位置变化了，但是后续还需要定位元素在原数组中的位置。此时建立原数组的索引数组，例如 nums = [5, 2, 6, 1], 索引数组为 indexes = [0, 1, 2, 3]，在算法流程中，nums 始终保持不变，改变位置的是 indexes 中的元素，以前是算法完成后需要 nums[i] 有序的性质，现在是要 nums[indexes[i]] 有序的性质。

有类似的思想的结构还有索引堆：堆在插入，更新数据之后，需要做一步向下更新或向上更新，这一步堆数据在数组中的位置就变了。但是有时在堆的不断更新过程中，需要定位到元素在堆数组中的位置，例如 239. 滑动窗口最大值，此时使用索引堆，保存堆数据的数组始终保持不变，不断更新位置的是索引数组。原来在更新算法流程中始终对 nums[i] 保持堆的性质，现在是对 nums[index[i]] 保持堆的性质。

代码 (C++)

代码与朴素归并排序基本相同，以前 nums[i] 改变位置的地方，改为 indexes[i] 改变位置，以前给定 i 获取 nums[i] 的地方，改为获取 nums[indexes[i]]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        if(nums.empty()) return vector<int>();
        int n = nums.size();
        if(n == 1) return vector<int>({0});
        vector<int> indexes(n, 0);
        for(int i = 1; i < n; ++i)
            indexes[i] = i;
        vector<int> result(n, 0);
        _mergesort(nums, indexes, result, 0, n - 1);
        return result;
    }

private:
    void _mergesort(const vector<int>& nums, vector<int>& indexes, vector<int>& result, int left, int right)
    {
        if(left == right) return;
        int mid = left + (right - left) / 2;
        _mergesort(nums, indexes, result, left, mid);
        _mergesort(nums, indexes, result, mid + 1, right);
        _merge(nums, indexes, result, left, mid, right);
    }

    void _merge(const vector<int>& nums, vector<int>& indexes, vector<int>& result, int left, int mid, int right)
    {
        vector<int> tmp(right - left + 1, 0);
        int i = left, j = mid + 1, k = 0;
        while(i <= mid && j <= right)
        {
            int pi = nums[indexes[i]], qj = nums[indexes[j]];
            if(pi <= qj)
            {
                result[indexes[i]] += (j - mid - 1);
                tmp[k++] = indexes[i++];
            }
            else
                tmp[k++] = indexes[j++];
        }
        while(i <= mid)
        {
            result[indexes[i]] += (j - mid - 1);
            tmp[k++] = indexes[i++];
        }
        while(j <= right) tmp[k++] = indexes[j++];
        for(i = left, k = 0; i <= right; ++i, ++k)
            indexes[i] = tmp[k];
    }
};
Share