算法数据结构

结合链表容易删除的特点使用逆向思维

字数统计: 1.3k字   |   阅读时长: 6分
,

摘要: 链表易于删除节点，方便维护逆向思维

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

逆向思维是一种常见的算法思维方式，在文章 逆向思维 中，我们例举了不少 leetcode 上用逆向思维解决的问题。

链表由于有易于删除的特点，因此经常与逆向思维结合使用。

在例如在文章 加索引的数组，用数组模拟双向循环链表 中我们解决的 136. 邻值查找。

本文我们再看一个类似的题 106. 动态中位数，本题的主流解法是 对顶堆，它是在线算法。这里我们用基于链表和逆向思维的离线算法。

问题：106. 动态中位数

依次读入一个整数序列，每当已经读入的整数个数为奇数时，输出已读入的整数构成的序列的中位数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入格式
第一行输入一个整数 P，代表后面数据集的个数，接下来若干行输入各个数据集。
每个数据集的第一行首先输入一个代表数据集的编号的整数。

数据集的剩余行由数据集的数据构成，每行包含 10 个数据，最后一行数据量可能少于 10 个，数据之间用空格隔开。

输出格式
对于每个数据集，第一行输出两个整数，分别代表数据集的编号以及输出中位数的个数（应为数据个数加一的二分之一），数据之间用空格隔开。
数据集的剩余行由输出的中位数构成，每行包含 10 个数据，最后一行数据量可能少于 10 个，数据之间用空格隔开。
输出中不应该存在空行。

数据范围
1<=P<=1000,
1<=M<=99999,
所有 M 相加之和不超过 5×1e5。

输入样例：
3
1 9
1 2 3 4 5 6 7 8 9
2 9
9 8 7 6 5 4 3 2 1
3 23
23 41 13 22 -3 24 -31 -11 -8 -7
3 5 103 211 -311 -45 -67 -73 -81 -99
-33 24 56
输出样例：
1 5
1 2 3 4 5
2 5
9 8 7 6 5
3 12
23 23 22 22 13 3 5 5 3 -3
-7 -3

算法：逆向思维

先把整个序列读入，排序后，一次插入一个链表，此时我们知道整个序列的中位数 P。

然后按照读入顺序从后向前，把数字从链表中删去。

删除的时候，要能够从原序列的索引对应到链表节点，通过一个索引数组实现即可。

整个算法及其实现过程与 用数组模拟双向循环链表 中对邻值查找那道题的解法几乎一样。

代码 (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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

struct Node
{
    int value;
    int prev, next;
};

const int SIZE = 2e5;
Node node[SIZE];
int head, tail, tot;
// tot 表示 node 数组已使用的最右位置，而不是链表长度

void init()
{
    tot = 2;
    head = 1;
    tail = 2;
    node[head].next = tail;
    node[tail].prev = head;
}

int insert(int p, int val)
{
    // 在 p 后插入新节点，数据为 val
    int tmp = ++tot;
    node[tmp].value = val;
    node[node[p].next].prev = tmp;
    node[tmp].next = node[p].next;
    node[p].next = tmp;
    node[tmp].prev = p;
    return tmp;
}

void remove(int p)
{
    // 删除节点 p
    node[node[p].prev].next = node[p].next;
    node[node[p].next].prev = node[p].prev;
}

void recycle()
{
    memset(node, 0, sizeof(node));
    head = tail = tot = 0;
}

struct Item
{
    int val;
    int idx; // 反向索引
    Item(){}
    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 P;
    cin >> P;

    for(int x = 1; x <= P; ++x)
    {
        // 输入
        int idx, n;
        cin >> idx >> n;
        vector<Item> vec(n);
        for(int j = 0; j < n / 10; ++j)
        {
            for(int k = 0; k < 10; ++k)
            {
                int v;
                cin >> v;
                vec[j * 10 + k] = Item(v, j * 10 + k);
            }
        }
        for(int k = 0; k < n % 10; ++k)
        {
            int v;
            cin >> v;
            vec[(n / 10) * 10 + k] = Item(v, (n / 10) * 10 + k);
        }
        sort(vec.begin(), vec.end(), Cmp());

        // 链表
        init();
        vector<int> indexes(n);
        for(int i = 0; i < n; ++i)
        {
            int nodeidx = insert(node[tail].prev, i);
            indexes[vec[i].idx] = nodeidx;
        }

        // 枚举
        int m = (n + 1) / 2;
        cout << idx << " " << m << endl;
        vector<int> result(m);
        int median_node = head;
        for(int i = 0; i < (n + 1) / 2; ++i)
        {
            median_node = node[median_node].next;
        }
        result[m - 1] = vec[node[median_node].value].val;
        for(int i = n - 1; i >= 1; --i)
        {
            int nodeidx = indexes[i];
            if(i & 1)
            {
                if(node[nodeidx].value <= node[median_node].value)
                    median_node = node[median_node].next;
                result[(i + 1) / 2 - 1] = vec[node[median_node].value].val;
            }
            else
            {
                if(node[nodeidx].value >= node[median_node].value)
                    median_node = node[median_node].prev;
            }
            remove(nodeidx);
            indexes[i] = tail;
        }

        for(int i = 0; i < m / 10; ++i)
        {
            for(int j = 0; j < 10; ++j)
                cout << result[i * 10 + j] << " ";
            cout << endl;
        }
        if(m % 10 > 0)
        {
            for(int j = 0; j < m % 10; ++j)
                cout << result[(m / 10) * 10 + j] << " ";
            cout << endl;
        }
    }
}
Share