[数据结构与算法]DAY 21冲击蓝桥杯——Python数据结构与算法03 数组Array

3.1 定义：

在连续的内存空间中，储存一组相同类型的元素。
二维数组实际是一个线性数组存放着其他数组的首地址。

3.2 区分：

3.2.1 元素VS索引

[1,2,3]
0,1,2

3.2.2 数组访问VS数组搜索

数组访问a[1]=2
数组搜索 找到这个元素

3.2.3 常见四种操作

数组常见四种操作时间复杂度
访问 O(1) 通过计算可以得到地址位置，从而进行访问
搜索 O(N) 需要对数组进行遍历
插入 O(N) 需要将后面的元素往后移动
如果内存不够，需要开辟一块新空间，将数组移进去
删除 O(N) 需要将后面元素往前移

3.3 特点

适合读
不适合频繁做增删操作。
场景：读多写少

3.4 python数组常用操作

3.4.1 创建数组

a=[] #注意括号里必须相同类型 否则为列表

3.4.2 添加元素

a.append() # 时间复杂度为O(1)或者O(n)，O(1)为尾部添加、O(n)是指另找位置存储
a.insert(2,99); # O(n)

3.4.3 访问元素

用索引（下标）访问元素

# O(1)
temp=a[2]

3.4.4 更新元素

用索引（下标）访问元素

# O(1)
a[2]=88

3.4.5 删除元素

a.remove(88) # O(n) 找到88这个元素
a.pop(1) # O(n) 删掉索引为1后需要整体往前移动一个单位 
a.pop() # O(1) 删掉末尾 不需要移动 

3.4.6 获取数组长度

a=[1,2,3]
size=len(a)
print(size)

3.4.7 遍历数组

# O(n)
for i in a:
	print(i)
for index,element in enumerate(a):
	print("index at",index,"is:",element)
for i in range(0,len(a)):
	print("i:",i,"element",a[i])

3.4.8 查找某个元素

index=a.index(2) # O(n) 从头到尾遍历
print(index)

3.4.9 数组排序

# O(nLog n)
a=[3,1,2]
a.sort() # 从小到大
print(a)
a.sort(reverse=True) # 从大到小
print(a)