【算法与数据结构】数组

前言

本系列专注更新基本数据结构，现以更新：

【算法与数据结构】数组.

【算法与数据结构】哈希表.

数组

数组的定义

数组是一种在内存中有着一块连续的内存空间的，并且由相同类型的元素组成的线性数据结构。以整数数组为例，数组的存储方式如下图所示：

在上图中可以看出数组在计算机中就是内存中一块连续的存储单元。数据元素的内存地址表示的就是该元素存放在内容中的地址，因为整型数据占据四个字节大小的内存，所以相邻两个元素地址之间相差 4。

在上图所示的数组中，数据元素的个数为 7，并且数组中都是整型元素。数组中每一个元素都可以通过「下标索引」来获取。下标索引从 0 开始（在计算机中数数都是从 0 开始），到数据元素的个数减一。

之所以称数组是一种线性数据结构是因为数组中所有数据元素排成像一条线一样的结构，每个数据元素最多只有前、后两个方向。链表、栈、队列这几种数据结构也有这样的线性特征。

数组的基本操作

几乎所有的数据结构都会涉及到增、删、改、查四个基本操作，数组也不例外。

增加元素

增加元素之前需要先检查数组是否已经满了（达到最大容量），如果满了就需要重新在内存中找到一块连续的地方放置原来数组中的元素以及新加入的元素。如果使用的是 C++ 中的 vector 容器，就不用担心容量不够的问题，因为在数组容量不够时 vector 会自动扩容。通常在数组尾部增加元素的时间复杂度为 $O(1)$。

如果在数组 nums 中位置 i 处插入一个新的元素 val，通常有以下步骤：

• 先检查 i 是否有效，即在数组的下标范围内；
• 确认有效后，检查数组 i 处是否已经存在元素了：
  • 没有元素当然好，直接更新 nums[i] = val；
  • 但是通常会有元素，这时候就需要将 i 及之后位置的元素向后挪动一个位置，然后将 val 放在空出来的位置 i 处。
• 这种插入情况最坏的时间复杂度为 $O(n)$，$n$ 是整个数组的长度。

这里就不考虑插入元素时数组满了的问题了，因为在 C++ 程序中通常都使用 vector 作为数组，这样一旦满了就会自动扩容。

删除元素

删除元素也分几种情况：

• 删除数组尾部元素，直接将数字计数值减一即可，这通常是 C 语言中的做法。前面已经说了 C++ 中几乎都用 vector 这个可动态扩容的数组，于是删除尾部元素直接 pop_back()。在 Python3 中直接 pop()。
• 删除数组 nums 中位置 i 的元素，通常有两个方法，当然在使用两个方法之前都要先检查 i 是否有效：
  • 借助临时数组：将原数组 nums 中除了 i 位置表示的元素之外的所有元素复制到临时数组中，然后清空数组 nums，最后再将临时数组中元素复制到 nums 中。这种方法需要遍历两次数组，渐进时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。
  • 原地操作：利用 i 位置后一位置的元素去覆盖 i 位置，即 i+1 位置的元素去覆盖 i 位置的元素，i+2 位置的元素去覆盖 i+1 位置的元素，以此类推，直到 i = n，最后再把最有一个元素删掉。时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。通常有关原地删除数组中元素的操作指的就是 覆盖。
• 最后一种情况就是「基于特定条件进行删除」，那就需要遍历数组，根据条件筛选出需要删除的元素或位置，一个个删除就好了。

通常删除操作的时间复杂度为 $O(n)$。

修改元素

这种操作就简单了。通过遍历数组找到需要修改的元素，直接修改即可。这种操作的时间复杂度为 $O(n)$。

查找元素

这种操作也很简答。如果是查找指定下标的元素，直接进行索引查找即可，时间复杂度为 $O(1)$。如果需要查找指定元素，那也不难，一次遍历即可，时间复杂度为 $O(n)$。

C++ STL 中的数组

在 C++ 标准库中定义两种类型的数组：array 和 vector。

array

array 是一种定长数组，也就是 C/C++ 中描述并使用的那种数组，使用之前要定义数组中的数据类型和固定的数组长度。

初始化

#include <iostream>
#include <array>	// array 的头文件

using namespace std;

int main() {
    
	// 初始化列表 初始化 
    array<int, 7> myArr = {1, 4, 6, 8, 9, 1, 3};
	
	
	// 拷贝初始化
	array<int, 7> myArr2 = myArr;
	
	for (const auto& num : myArr2) {
		cout << num << " ";
	}
	
	return 0;
}

array 有两种初始化方法：初始化列表初始化和拷贝初始化。

重要的成员函数

vector

vector 是一种容器，是一种可变长的数据。当向 vector 容器中增加数据时，如果容器已经满了，那么它会重新在内存中找一块更大的连续内存来存放原来的数据。通常是按照原来内存的两倍大小进行扩容的。得益于自动扩容的特性，C++ 中多使用 vector 来构造数组。

初始化（构造函数）

#include <iostream>
#include <vector>

int main () {
  // constructors used in the same order as described above:
  std::vector<int> first;                                // empty vector of ints
  std::vector<int> second (4,100);                       // four ints with value 100
  std::vector<int> third (second.begin(),second.end());  // iterating through second
  std::vector<int> fourth (third);                       // a copy of third

  // the iterator constructor can also be used to construct from arrays:
  int myints[] = {16,2,77,29};
  std::vector<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );

  std::cout << "The contents of fifth are:";
  for (std::vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

重要的成员函数

Python3 中的列表

python 中没有固定长度的数组，只有类似于 vector 容器的列表。

列表是一个有序且可更改的集合。集合中可以混合放置任意类型的元素，比如文本类型、数值类型和布尔类型，不要求必须放置同一类型的元素。

list1 = [8, "srt", 98, True]

此例中，列表 list1 包含了数值类型，文本类型和布尔类型的数据元素。

访问

可以通过索引来访问列表。

list1 = [8, "str", 98, True]

print(list1[0]) # 输出 "str"

在 Python3 中索引可以是负值，负值索引表示从列表的末尾开始访问，-1 表示列表的最后一个元素，-2 表示列表的倒数第二个元素，等等。

list1 = [8, "str", 98, True]

print(list1[-1]) # 输出列表的最后一个元素 True

范围索引

可以对列表指定起点、终点（取不到）和步长进行范围索引。

list2 = [1, 4, 5, 6]

print(list2[0 : 3 : 2])	# 输出 [1, 5]

此例子对列表 list2 进行范围索引，从索引 0 开始，到索引 3 结束，每次在上一个索引的基础上 +2 进行访问。

负范围索引

范围索引还可以是负值。

list2 = [1, 4, 5, 6]

print(list2[-4 : -1 : 2]) # 仍然输出 [1, 5]

此例子对列表 list2 进行负的范围索引，从倒数第 4 个元素开始索引，到倒数第一个元素结束（取不到），每次在上一个索引的基础上 +2 进行访问。

更改元素值

通过使用索引轻松更改元素值。

list2 = [1, 4, 5, 6]
list2[0] = 0	# 将列表第一个元素更改为 0

print(list2)	# 输出 [0, 4, 5, 6]

遍历列表

可以像 C/C++ 一样使用索引进行遍历，Python3 有自己的一种 for 遍历方法，C++ 中的 for 范围遍历对应的就是 Python3 中的范围遍历。

list3 = ["apple", "pear", "pineapple"]

for x in list3:
	print(x)

# 输出
"""
"apple"
"pear"
"pineapple"
"""

检查列表中是否存在某元素

如果需确定列表中是否存在指定的元素，使用 in 关键字：

list3 = ["apple", "pear", "pineapple"]

if "apple" in list3:
	print("Yes, 'apple' is in the fruits list3.")

在此例中，如果文本 “apple” 在列表 list3 中，则 if 条件语句为 True，执行对应的语句，输出 "Yes, 'apple' is in the fruits list3.".

增加元素

如需将元素添加到列表的末尾，使用 append() 方法：

list3 = ["apple", "pear", "pineapple"]
list3.append("banana")

print(list3) # 输出 ["apple", "pear", "pineapple", "banana"]

要在指定的索引处添加元素，使用 insert() 方法：

list4 = ["apple", "pear", "pineapple"]
list4.insert(1, "cherry")

print(list4)	# 输出 ["apple",  "cherry", "pear", "pineapple"]

此例中，在列表 lsit4 的索引 1 处插入 “cherry”。

删除元素

通过 remove() 删除指定元素：

list5 = ["apple", "cherry", "pear", "pineapple"]
list5.remove("apple")

print(list5)	# 输出 ["cherry", "pear", "pineapple"]

通过 pop() 删除指定索引的元素（如果没有指定索引，则删除最后一项）：

list6 = ["cherry", "pear", "pineapple"]
list6.pop()

print(list6)	# 输出 ["cherry", "pear"]

使用 del 关键字删除指定的索引，del 关键字也能完整地删除列表：

list7 = ["cherry", "pear", "pineapple"]
del list7[0]
print(list7)	# 输出 ["pear", "pineapple"]

del list7       # 直接删除 list7 

使用 clear() 方法清空列表，这一点和 vector 中的 `clear() 一样：

list8 = ["apple", "banana", "cherry"]
list8.clear()

print(list8)   # 输出 []

拷贝列表

拷贝列表分为浅拷贝和深拷贝。见 Python之赋值、深拷贝与浅拷贝

总结 Python3 列表的常用操作

参考资料

【文章】01. 数组基础知识

【文章】Python 列表

写在最后

如果您发现文章有任何错误或者对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家觉得有些地方需要补充，欢迎评论区交流。

最后，感谢您的阅读，如果有所收获的话可以给我点一个 👍 哦。