题目类型总结
最近在阅读《算法竞赛进阶指南》这本书的链表这一节时，学会了链表在一类特定问题中的巧妙用法，遂有此文，也算是自己的一个学习笔记。
考虑这样一类问题，一个长度为\(n\)的序列，有\(q\)询问，询问序列前任意个数的一个结果，该结果可通过暴力排序后直接判断，但是这种方法显然很暴力，很容易达到\(O(qn\log n)\)的复杂度。
使用链表进行优化，先将序列全部读进来后进行排序，之后通过删除操作达到前任意段排完序后的序列。此时，只需进行一次排序，后面直接进行删除操作即可，效率大幅上升。
例题
该做法的一个经典应用即动态中位数问题，即一段长度为\(n\)的序列，依次输出前\(i\)个数的中位数，当然做法不止一种，这里讨论链表做法。
将\(n\)个数读进来，进行一个序的排，然后按顺序建立链表，同时建立辅助数组，存储每个数在链表里的位置。
首先可以找到\(n\)个数时的中位数，然后讲第\(n\)个数从链表中删去，如果这个数在链表中的位置在中位数之前，将中位数指针向后移动即可，相反的向前移动。
重复此操作，得到所有位置的答案。时间复杂度\(O(n\log n)\)
练习题
SPOJ15376 RMID - Running Median /Acwing 106. 动态中位数
标签：复杂度,个数,中位数,链表,序列,排序,巧用 From： https://www.cnblogs.com/six-one/p/17124837.html