数据结构与算法: 数组

本系列文章是在学习数据结构和算法时记录的学习笔记,概念讲解部分主要引用自《极客时间》的相关专栏,代码实践部分由本人采用 Python 实现。
版权归极客时间所有

概念

数组(Array)是一种线性表数据结构,它用一组连续的内存空间,来存储一组具有相同类型的数据。

数组有两个最大的特点:

  • 线性表数据结构:线性表(Linear List)就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。数组,链表、队列、栈 都是线性表结构。与之对应的是非线性表数据结构,如二叉树、堆、图等。
  • 连续的内存空间和相同类型的数据

线性表 vs. 非线性表


复杂度分析

数组具有如下特性:

  • 非常高效的“随机访问”:通过下标访问只需一次操作即可获取到数据
  • 低效的“插入”和“删除”:插入和删除后,需要同时移动数组中的其它数据

对应的时间复杂度如下:

  • Access: O(1)
  • Insert: 最小 O(1),最大 O(n),平均 O(n)
  • Delete: 最小 O(1),最大 O(n),平均 O(n)

注意:数组的查询操作并非为 O(1),即便是排好序的数组,采用二分查找,时间复杂度也是 O(logn)。

代码实践

典型问题

1、实现一个支持动态扩容的数组 🤔

TODO
1
2
3
class Array(object):
def __init__(self):
pass

2、实现一个大小固定的有序数组,支持动态增删改操作 🤔

TODO

3、实现两个有序数组合并为一个有序数组 🤔

TODO

LeetCode

debugtalk/geekcode

引用

debugtalk wechat
欢迎关注「DebugTalk」,获取本站最新内容。