数组基础知识内容优化

itcharge · itcharge · commit 75d30389b0fb · 2023-08-24T20:01:21.000+08:00
diff --git a/Contents/01.Array/01.Array-Basic/01.Array-Basic.md b/Contents/01.Array/01.Array-Basic/01.Array-Basic.md
@@ -76,10 +76,6 @@ arr = ['python', 'java', ['asp', 'php'], 'c']
 > 1. 只需要检查 $i$ 的范围是否在合法的范围区间，即 $0 \le i \le len(nums) - 1$。超出范围的访问为非法访问。
 > 2. 当位置合法时，由给定下标得到元素的值。
 
-访问操作不依赖于数组中元素个数，因此时间复杂度为 $O(1)$。
-
-示例代码如下：
-
 ```python
 # 从数组 nums 中读取下标为 i 的数据元素值
 def value(nums, i):
@@ -90,6 +86,8 @@ arr = [0, 5, 2, 3, 7, 1, 6]
 value(arr, 3)
 ```
 
+「访问数组元素」的操作不依赖于数组中元素个数，因此，「访问数组元素」的时间复杂度为 $O(1)$。
+
 ### 2.2 查找元素
 
 > **查找数组中元素值为 $val$ 的位置**：
@@ -98,10 +96,6 @@ value(arr, 3)
 > 2. 在找到元素的时候返回元素下标。
 > 3. 遍历完找不到时可以返回一个特殊值（例如 $-1$）。
 
-在数组无序的情况下，只能通过将 $val$ 与数组中的数据元素逐一对比的方式进行检索，也称为线性查找。线性查找操作依赖于数组中元素个数，因此时间复杂度为 $O(n)$。
-
-示例代码如下：
-
 ```python
 # 从数组 nums 中查找元素值为 val 的数据元素第一次出现的位置
 def find(nums, val):
@@ -114,6 +108,8 @@ arr = [0, 5, 2, 3, 7, 1, 6]
 print(find(arr, 5))
 ```
 
+在「查找元素」的操作中，如果数组无序，那么我们只能通过将 $val$ 与数组中的数据元素逐一对比的方式进行查找，也称为线性查找。而线性查找操作依赖于数组中元素个数，因此，「查找元素」的时间复杂度为 $O(n)$。
+
 ### 2.3 插入元素
 
 插入元素操作分为两种：「在数组尾部插入值为 $val$ 的元素」和「在数组第 $i$ 个位置上插入值为 $val$ 的元素」。
@@ -123,55 +119,47 @@ print(find(arr, 5))
 > 1. 如果数组尾部容量不满，则直接把 $val$ 放在数组尾部的空闲位置，并更新数组的元素计数值。
 > 2. 如果数组容量满了，则插入失败。不过，Python 中的 list 列表做了其他处理，当数组容量满了，则会开辟新的空间进行插入。
 
-在尾部插入元素的操作不依赖数组个数，其时间复杂度为 $O(1)$。
-
 Python 中的 list 列表直接封装了尾部插入操作，直接调用 `append` 方法即可。
 
 ![插入元素](https://qcdn.itcharge.cn/images/20210916222517.png)
 
-示例代码如下：
-
 ```python
 arr = [0, 5, 2, 3, 7, 1, 6]
 val = 4
 arr.append(val)
 print(arr)
 ```
 
+「在数组尾部插入元素」的操作不依赖数组个数，因此，「在数组尾部插入元素」的时间复杂度为 $O(1)$。
+
 > **在数组第 $i$ 个位置上插入值为 $val$ 的元素**：
 >
 > 1. 先检查插入下标 $i$ 是否合法，即 $0 \le i \le len(nums)$。
 > 2. 确定合法位置后，通常情况下第 $i$ 个位置上已经有数据了（除非 $i == len(nums)$），要把第 $i \sim len(nums) - 1$ 位置上的元素依次向后移动。
 > 3. 然后再在第 $i$ 个元素位置赋值为 $val$，并更新数组的元素计数值。
 
-因为移动元素的操作次数跟元素个数有关，最坏和平均时间复杂度都是 $O(n)$。
-
 Python 中的 list 列表直接封装了中间插入操作，直接调用 `insert` 方法即可。
 
 ![插入中间元素](https://qcdn.itcharge.cn/images/20210916224032.png)
 
-示例代码如下：
-
 ```python
 arr = [0, 5, 2, 3, 7, 1, 6]
 i, val = 2, 4
 arr.insert(i, val)
 print(arr)
 ```
 
+「在数组中间位置插入元素」的操作中，由于移动元素的操作次数跟元素个数有关，因此，「在数组中间位置插入元素」的最坏和平均时间复杂度都是 $O(n)$。
+
 ### 2.4 改变元素
 
 > **将数组中第 $i$ 个元素值改为 $val$**：
 >
 > 1. 需要先检查 $i$ 的范围是否在合法的范围区间，即 $0 \le i \le len(nums) - 1$。
 > 2. 然后将第 $i$ 个元素值赋值为 $val$。
 
-改变元素操作跟访问元素操作类似，访问操作不依赖于数组中元素个数，因此时间复杂度为 $O(1)$。
-
 ![改变元素](https://qcdn.itcharge.cn/images/20210916224722.png)
 
-示例代码如下：
-
 ```python
 def change(nums, i, val):
     if 0 <= i <= len(nums) - 1:
@@ -183,6 +171,8 @@ change(arr, i, val)
 print(arr)
 ```
 
+「改变元素」的操作跟访问元素操作类似，访问操作不依赖于数组中元素个数，因此，「改变元素」的时间复杂度为 $O(1)$。
+
 ### 2.5 删除元素
 
 删除元素分为三种情况：「删除数组尾部元素」、「删除数组第 $i$ 个位置上的元素」、「基于条件删除元素」。
@@ -191,54 +181,47 @@ print(arr)
 >
 > 1. 只需将元素计数值减一即可。
 
-这样原来的数组尾部元素不再位于合法的数组下标范围，就相当于删除了。时间复杂度为 $O(1)$。
-
 Python 中的 list 列表直接封装了删除数组尾部元素的操作，只需要调用 `pop` 方法即可。
 
 ![删除尾部元素](https://qcdn.itcharge.cn/images/20210916233914.png)
 
-示例代码如下：
-
 ```python
 arr = [0, 5, 2, 3, 7, 1, 6]
 arr.pop()
 print(arr)
 ```
 
+「删除数组尾部元素」的操作，不依赖于数组中的元素个数，因此，「删除数组尾部元素」的时间复杂度为 $O(1)$。
+
 > **删除数组第 $i$ 个位置上的元素**：
 >
 > 1. 先检查下标 $i$ 是否合法，即 $0 \le i \le len(nums) - 1$。
 > 2. 如果下标合法，则将第 $i + 1$ 个位置到第 $len(nums) - 1$ 位置上的元素依次向左移动。
 > 3. 删除后修改数组的元素计数值。
 
-删除中间位置元素的操作同样涉及移动元素，而移动元素的操作次数跟元素个数有关，因此删除中间元素的最坏和平均时间复杂度都是 $O(n)$。
-
 Python 中的 list 列表直接封装了删除数组中间元素的操作，只需要以下标作为参数调用 `pop` 方法即可。
 
 ![删除中间元素](https://qcdn.itcharge.cn/images/20210916234013.png)
 
-示例代码如下：
-
 ```
 arr = [0, 5, 2, 3, 7, 1, 6]
 i = 3
 arr.pop(i)
 print(arr)
 ```
 
-> **基于条件删除元素**：这种操作一般不给定被删元素的位置，而是给出一个条件要求删除满足这个条件的（一个、多个或所有）元素。这类操作也是通过循环检查元素，查找到元素后将其删除。
-
-删除多个元素操作中涉及到的多次移动元素操作，可以通过算法改进，将多趟移动元素操作转变为一趟移动元素，从而将时间复杂度降低为 $O(n)$。一般而言，这类删除操作都是线性时间操作，时间复杂度为 $O(n)$。
+「删除数组中间位置元素」的操作同样涉及移动元素，而移动元素的操作次数跟元素个数有关，因此，「删除数组中间位置元素」的最坏和平均时间复杂度都是 $O(n)$。
 
-示例代码如下：
+> **基于条件删除元素**：这种操作一般不给定被删元素的位置，而是给出一个条件要求删除满足这个条件的（一个、多个或所有）元素。这类操作也是通过循环检查元素，查找到元素后将其删除。
 
 ```python
 arr = [0, 5, 2, 3, 7, 1, 6]
-i = 3
 arr.remove(5)
 print(arr)
 ```
 
+「基于条件删除元素」的操作同样涉及移动元素，而移动元素的操作次数跟元素个数有关，因此，「基于条件删除元素」的最坏和平均时间复杂度都是 $O(n)$。
+
 ---
 
 到这里，有关数组的基础知识就介绍完了。下面进行一下总结。
@@ -247,7 +230,7 @@ print(arr)
 
 数组是最基础、最简单的数据结构。数组是实现线性表的顺序结构存储的基础。它使用一组连续的内存空间，来存储一组具有相同类型的数据。
 
-数组的最大特点的支持随机访问。其访问元素、改变元素的时间复杂度为 $O(1)$，在尾部插入、删除元素的时间复杂度也是 $O(1)$，普通情况下插入、删除元素的时间复杂度为 $O(n)$。
+数组的最大特点的支持随机访问。访问数组元素、改变数组元素的时间复杂度为 $O(1)$，在数组尾部插入、删除元素的时间复杂度也是 $O(1)$，普通情况下插入、删除元素的时间复杂度为 $O(n)$。
 
 ## 参考资料
 
