20220815笔记
-
说说常用的排序算法和其时间复杂度
-
100万用户如何根据年龄排序
-
深度优先和广度优先搜索算法
-
如何快速获取Top10热门搜索关键词
-
单向链表反转怎么实现?
-
如何判断链表有环
-
如何找到单向链表的中间元素
说说常用的排序算法和其时间复杂度
| 类别 | 排序方法 | 时间复杂度 | 空间复杂度 | 稳定性 | ||
|---|---|---|---|---|---|---|
| 平均情况 | 最好情况 | 最坏情况 | 辅助存储 | |||
| 插入排序 | 直接插入 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
| Shell排序 | O(n1.3) | O(n) | O(n2) | O(1) | 不稳定 | |
| 选择排序 | 直接选择 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 |
| 堆排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(1) | 不稳定 | |
| 交换排序 | 冒泡排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
| 快速排序 | O(nlog2n) | O(nlog2n) | O(n2) | O(1) | 不稳定 | |
| 归并排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(n) | 稳定 | |
| 基数排序 | O(d(r+n)) | O(d(n+rd) | O(d(n+r)) | O(rd+n) | 稳定 |
注:基数排序的复杂度中，r表示关键字的基数，d表示长度，n表示关键字的个数
100万用户如何根据年龄排序
可以通过桶排序、基数排序、基数排序
-
桶排序：把数据分到M个桶内，希望桶内的数据实现均匀的，并且桶与桶之间有着天然额大小顺序。极端情况下会退化成O(nlogn)，比较适合外部排序，在进行划分同数据的时候，可能出现桶数据不均匀的情况，可以选择再多的数据桶内继续划分桶，直到桶数据可以加载到内存中为止。
将用户按预估年龄合理划分桶的数量，之后将用户简单分组至桶中，再分别对桶内数据按照常用排序算法进行排序，全部完成以后再将桶进行排序得出最终结果。
-
计数排序：将数据逐一统计不同数据的数量，再将其按照排序规则逐一输出以得到最终结果。
年龄排序可以创建1-100的的数组，遍历数据将其按照年龄将对应索引的值自增。完成以后从小到大输出索引，同时值自减直至为零再跳到下一个索引。
-
基数排序：基数排序和计数排序有点类似,不过不是整个数据一起判断,而是先排个位,再排十位以此类推..
深度优先和广度优先搜索算法
-
广度优先算法：一般称为BFS，在查找的时候一层一层的向前查找，直到找到目标。比较适合图的搜索，例如多个站点，找出两个站点之间最近的路线。
一般通过三个属性记录：
- visited：一个布尔数组，记录节点是否被访问过，访问过为真，没有则为假。
- vertex：记录上一层的顶点，用来访问当前层其他还没有访问的节点。
- prev：记录搜索路径，保存当前节点的路径，以便输出结果。
-
深度优先算法：一般称为DFS，查找的时候先从一个节点往下搜索到底，没有找到则回溯。比较适合树的查找，例如走迷宫问题。
在走迷宫问题中先随意走一个路口，直到走到尽头，发现出口则直接返回，没有的话就回溯往回走，继续下一个路口。
如何快速获取Top10热门搜索关键词
可以通过优先级队列实现，一般队列是遵循先进先出原则，而优先级队列不是。在优先级队列中数据的出队顺势是根据优先级来的，优先级越高越先出队。
单向链表反转怎么实现?
首先将头节点指向第二个节点，之后获取第二个节点，将其指向第三个节点。。以此类推，直到完全遍历转换完成。
如何判断链表有环
设定两个指针，分别为one、two。
两指针都是从头节点开始，one指针每次前进一步，two指针每次前进两步，一直前进，直到遇到尾节点或者两指针相等时退出。
如何找到单向链表的中间元素
跟上一问差不多。
设定两个指针，分别为one、two。
两指针都是从头节点开始，one指针每次前进一步，two指针每次前进两步，一直前进，当two节点为空时，one节点所处位置即为中间节点。
本文使用 文章同步助手 同步
