链表巧用

题目类型总结

最近在阅读《算法竞赛进阶指南》这本书的链表这一节时,学会了链表在一类特定问题中的巧妙用法,遂有此文,也算是自己的一个学习笔记。

考虑这样一类问题,一个长度为\(n\)的序列,有\(q\)询问,询问序列前任意个数的一个结果,该结果可通过暴力排序后直接判断,但是这种方法显然很暴力,很容易达到\(O(qn\log n)\)的复杂度。

使用链表进行优化,先将序列全部读进来后进行排序,之后通过删除操作达到前任意段排完序后的序列。此时,只需进行一次排序,后面直接进行删除操作即可,效率大幅上升。

例题

该做法的一个经典应用即动态中位数问题,即一段长度为\(n\)的序列,依次输出前\(i\)个数的中位数,当然做法不止一种,这里讨论链表做法。

\(n\)个数读进来,进行一个序的排,然后按顺序建立链表,同时建立辅助数组,存储每个数在链表里的位置。

首先可以找到\(n\)个数时的中位数,然后讲第\(n\)个数从链表中删去,如果这个数在链表中的位置在中位数之前,将中位数指针向后移动即可,相反的向前移动。

重复此操作,得到所有位置的答案。时间复杂度\(O(n\log n)\)

练习题

AcWing 136. 邻值查找

SPOJ15376 RMID - Running Median /Acwing 106. 动态中位数

[HNOI2002]营业额统计

热门相关:超武穿梭   霸皇纪   时间都知道   寂静王冠   霸皇纪