【面试】数据结构与算法(一)

2020

0x1、数据结构与算法绪论

要点：简单了解下概念，起码得知道「时间复杂度」和「空间复杂度」

0x2、顺序表

顺序表与数组都是数据结构，只是描述角度不同。顺序表是从逻辑结构的角度来说的，它的每一个元素都只有一个前驱元素和一个后驱元素除了头和尾，逻辑结构还有队列，堆栈，树，图等。而数组是从物理存贮的角度来说的，顺序表用数组存贮也可以用链表来存贮。同样的队列也可以用数组和链表存贮，各有利弊。

顺序表是「线性表」中的一种，而线性表的简单介绍如下：

「顺序表」和「链表」都属于线性表！顺序表具有如下特点：

• 「长度固定」需在分配内存前就确定长度，可用「倍增-复制」的办法来「动态扩容」
  (比如初始为4，超过申请一个长度为4*2的数组，然后把数据复制过去，让其看起来是可变长度的)
• 「存储空间连续」逻辑上有前后关系，物理存储也是前后相连的。
• 「空间利用率高」存储密度大，局部性原理，连续存放，命中率高。
• 「查找效率高」支持「随机访问」，「用下标随机访问」的时间复杂度为O(1)。
• 「插入和删除较慢」每次增删元素，需平均移动约表长一半的元素，时间复杂度O(n)。

基本操作中的难点是「插入」和「删除」通过动图了解一波流程：

从图片不难看出「插入」的要点「从后往前移动元素(赋值，i+1=>i)，直到遇到插入下标」

从图片不难看出「删除」的要点「从删除位置开始，从前往后移动元素(赋值，i=i+1)，直到到达表尾」

Tips：如果无法理解，可自行执行动画试试，或者用实物模拟帮助理解~

0x3、基本操作代码实现(基于Kotlin)

注：常用数组来描述顺序表，但要注意，线性表是从1开始算的，而数组下标却是从0开始的，
所以要访问表中第i个元素，需要减1，具体可在代码中提现！

先上运行结果：

具体代码实现(SeqList.kt)

0x4、经典例子——求并集

问题描述：

已知有A、B两个顺序表，元素按照从小到达排序，现在要你求两个表的并集C，且C中的元素页要按照从小到大排序，不能修改A和B中的数据。

解题思路：

• Step 1：构造表C，长度为A+B的元素个数之和；
• Step 2：定义两个指针(下标)，用于A和B元素寻址；
• Step 3：遍历，A<B 插入A元素、A下标++ => 插入B元素、B下标++，知道其中一个下标到尾；
• Step 4：剩下的元素要么是表A的，要么是表B的，直接循环遍历
• Step 5：为表C定义代表前后两个指针(下标)，遍历剔除重复元素

运行结果：

具体代码实现（UnionQuestion.kt）

源码地址：https://github.com/coder-pig/DataStructureNote