这道题就是区间插入问题,目前看到的解法主要有三种,一种是直接分析区间重叠,具有O(n)时间和O(n)空间复杂度,另一种是用二叉搜索树来做,还有一种是借助了STL库中的equal_range方法来做,写法比较优雅。这篇博客主要给出第一种解法和第三种解法的代码…

经典的线性时间排序问题,题目标签是hard,主要是要求了线性时间内解决问题,那么很自然想到基数排序和桶排序了。除此之外还有一种常用的线性时间排序,计数排序可以看做间隔为1的桶排序,在数字比较集中且可转化为整数时比较有效,因此计数排序不适合本题目。…

博主之前刷过一遍《算法导论》(Introduction to Algorithms),但是看得多写得少,于是最近抽空动手写写下里面的算法。排序是经典问题了,于是决定将书中的排序算法一一使用C++实现。这篇博客一方面是对排序算法本身的总结(这个书上都有啦),另一方面是博主在使用C++实现算法时的一些体会,更多的是算法细节,希望有助于加深对算法的理解的。…