数据结构与数组的基本介绍+Leetcode 704题解

数据结构的基本介绍

什么是数据结构

数据结构是计算机组织、存储数据的方式，包含数据本身、数据之间的关系，以及对数据的增删改查操作。同样的数据，选用不同数据结构，程序运行效率差别很大。算法是解决问题的步骤，数据结构是存放数据的容器，二者紧密配合。

两种物理存储方式

1.顺序存储

数据存放在连续的内存空间，比如数组、Python 列表。
优点：可以通过下标直接访问元素，速度快。
缺点：在中间位置插入、删除元素，需要移动很多数据，效率低。

2.链式存储

内存不连续，每个结点保存数据，同时记录下一个结点的位置，代表就是链表。
优点：插入删除只修改结点指向，不用移动大量数据。
缺点：不能直接随机访问，查找元素需要从头逐个遍历。

逻辑结构

1.线性结构：一对一的关系（元素排成一条直线，除开头尾，每个元素只有一个前驱和后继）

数组 / 列表：基础容器，依靠下标访问
链表：单链表、双向链表、循环链表
栈：后进先出，只能从同一端存取，用于括号匹配、函数调用
队列：先进先出，一端存一端取，用于任务排队、广度优先搜索

2.非线性结构

树：一对多（一个节点分出多个子节点。常见二叉树、二叉搜索树）
图：多对多（节点之间可以任意连接，边可以带权重、方向，用于地图路径、社交网络等场景）
集合：元素没有顺序，元素不可重复。

常见数据结构核心特点

数组：连续内存，适合二分、排序。
链表：适合频繁做插入删除。
栈：后进先出。
队列：先进先出。
二叉树：层级结构，用于搜索。
图：节点和边，处理路径类问题。

复杂度（用来衡量性能）

时间复杂度 O ()：描述数据变多的时候，程序运行时间增长的趋势。

O (1) 常数级，不受数据量影响
O (log n) 对数级，代表二分查找，每次舍弃一半数据
O (n) 线性级，需要遍历全部数据
O (nlogn)，常见高效排序算法
O (n²)，双重循环，效率较低

空间复杂度：算法额外占用内存的大小。O (1) 代表几乎不额外开辟内存。

复杂度只关注增长趋势，忽略常数。

逻辑结构和存储结构区分

1.逻辑结构指数据抽象出来的关系，比如栈逻辑上后进先出；
2.存储结构指在内存真实存放形式，栈既可以数组实现，也可以链表实现。

数组的基本概念

什么是数组

数组是最基础的线性顺序存储的数据结构。把多个相同类型的数据，存放在内存中一块连续的空间里。

核心特点

1.内存连续，所有元素挨在一起存放。
2.通过下标（索引）访问元素，下标一般从0开始。
3.随机访问：知道下标，就能直接取出对应元素，时间复杂度 O (1)。
4.存放的元素一般要求类型相同。

下标（索引）

第一个元素下标为 0，第二个为 1，依次往后。
例数组[5, 2, 7]
下标 0：5，下标 1：2，下标 2：7。
数组长度指的是数组里面一共有多少个元素。

常见操作以及效率

1.读取 / 修改指定下标元素：O (1)，直接定位，速度很快。
2.尾部添加元素：一般效率很高。
3.中间位置插入、删除元素：O (n)。
因为内存连续，插入或者删除后，后面所有元素都需要整体向后 / 向前移动。数据量大的时候效率低。
4.遍历数组：从头到尾逐个访问，O (n)。

数组优缺点

优点：
1.支持下标随机访问，查找指定位置速度快。
2.内存连续，缓存友好，遍历速度快。
缺点：
1.中间插入、删除代价大，需要移动大量元素。
2.很多语言数组长度固定，一旦创建，不能随意扩容

Leetcode 704+题解

题解：

在升序数组 nums 中寻找目标值 target，对于特定下标 i，比较 nums[i] 和 target 的大小：
1.如果 nums[i]=target，则下标 i 即为要寻找的下标；
2.如果 nums[i]>target，则 target 只可能在下标 i 的左侧；
3.如果 nums[i]<target，则 target 只可能在下标 i 的右侧。

因为定义查找的范围 [left,right]，所以初始查找范围是整个数组。每次取查找范围的中点 mid，比较 nums[mid] 和 target 的大小，如果相等则 mid 即为要寻找的下标，如果不相等则根据 nums[mid] 和 target 的大小关系将查找范围缩小一半。
二分查找的条件是查找范围不为空，即 left≤right。如果 target 在数组中，二分查找可以保证找到 target，返回 target 在数组中的下标。如果 target 不在数组中，则当 left>right 时结束查找，返回 −1。

左闭右闭 [left, right]

区间含义：left 与 right 下标对应的元素都参与查找。
right 初始值：len(nums)-1，数组最后一个元素下标。
while 循环条件：left <= right
当 left 等于 right，区间里面还有一个有效的元素，需要执行循环进行判断。

更新边界规则

nums [mid] > target → 目标在左侧，right = mid – 1
mid 已经比对完毕，不需要再次纳入查找区间。
nums [mid] < target → 目标在右侧，left = mid + 1

左闭右开 [left, right)

区间含义：包含 left，不包含 right 下标，right 仅仅作为边界。
right 初始值：len(nums)，它超出数组最大下标，不是合法元素。
while 循环条件：left < right
left 与 right 相等时，区间里面不存在元素，循环终止。

更新边界规则

nums [mid] > target → right = mid
mid 下标不在新区间，右边界直接赋值 mid。
nums [mid] < target → left = mid + 1