[关闭]
@coder-pig 2021-02-24T07:25:32.000000Z 字数 1086 阅读 219

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

2020


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


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


0x2、顺序表

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

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

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

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

从图片不难看出「插入」的要点「从后往前移动元素(赋值,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



添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注