2020-05-01 数组，链表以及跳表

1.数组的时间复杂度：append    -----O(1)      lookup -----O(1)    insert -----O(n)    delete-----O(n)

2.链表的时间复杂度：append    -----O(1)     lookup -----O(n)    insert -----O(1)    delete -----O(1)

选择哪种数据结构与业务系统有关，但是是否有一种数据结构能综合这两种的优点？引出今天的重点：跳表，也就是redis的zset的数据结构

3.skip list

特点：只能用于元素有序的情况，所以对标的是平衡树以及二分查找树，插入/删除/查找得失时间复杂度都是O(log n)

对于一维的数据进行加速，一般来说就是升为二维，也就是昨天说到的，利用空间换取时间，一级索引是N/2, 二级索引是N/4,空间复杂度为O(n), 如图

leet code刷题方法：

1.    5-10分钟思考

2. 有思路的话自己做题，一点思路没有赶紧写看题解

3.已有的题解背诵。默写直到熟料

4.复制题目，去掉cn，上国际站

5.高级算法模版

一道题刷五遍