python算法笔记——数组

Valentina ·

更新时间:2024-11-10

· 753 次阅读

概述

数据是最基本，最简单也是最常见的数据结构，属于线性结构的一种。在python中实现数组非常容易。比如，我们创建一个数组并进行一些基本操作：

数组的插入

my_list = [1,2,3,4,5,4,3,2,1]
print(my_list) #打印数组
my_list[0] = 0 # 将第一个位置更新为0
my_list.append(6) # 在最后一个位置添加元素6
my_list.insert(3,7) #在索引为3的位置插入7

但是，从算法的角度而言，我们要考虑每个操作的时间复杂度和空间复杂度。所以我们来自己实现一段插入操作的代码：

class MyArray:
    def __init__(self, capacity):
        self.array = [None] * capacity
        self.size = 0
    def insert(self, index, element):
        # 判断访问下标是否超出范围
        if index  self.size:
            raise Exception("超出数组实际元素范围！")
        # 从右向左循环，逐个元素向右挪一位。
        for i in range(self.size-1, index-1, -1):
            self.array[i+1] = self.array[i]
        # 腾出的位置放入新元素
        self.array[index] = element
        self.size += 1
    def output(self):
        for i in range(self.size):
            print(self.array[i])

这里的size是数组中元素的数量。如果在尾部插入元素，传入下标的index等于size，如果插入元素在数组的中间或者头部，index小于size。数组中间插入元素时，我们将索引位置到最后位置的元素的索引全部右移一位，然后空出来的位置放入新元素。
实例化看一下实现情况：

array = MyArray(4)
array.insert(0, 10)
array.insert(1, 11)
array.insert(2, 12)
array.insert(3, 13)
array.insert(4, 14)
array.insert(2, 15)
array.insert(2, 16)
array.insert(2, 17)
array.remove(0)
array.output()

数组扩容

我们考虑这样一个问题，如果我们不断得往数组中插入元素，某时数组得元素超过了数据定义时得长度（创建时长度已经确定了），那我们该怎么办呢？
扩容得想法应运而生。这时我们需要创建一个新的数组，长度是原来数组得两倍，把原来数组得内容复制过来，这样就实现了数组的扩容了。
此时，我们需要改写一下插入元素的方法：

 def insert_v2(self, index, element):
        # 判断访问下标是否超出范围
        if index  self.size:
            raise Exception("超出数组实际元素范围！")
        # 如果实际元素达到数组容量上线，数组扩容
        if self.size >= len(self.array):
            self.resize()
        # 从右向左循环，逐个元素向右挪一位。
        for i in range(self.size-1, index-1, -1):
            self.array[i+1] = self.array[i]
        # 腾出的位置放入新元素
        self.array[index] = element
        self.size += 1
    def resize(self):
        array_new = [None] * len(self.array) * 2
        # 从旧数组拷贝到新数组
        for i in range(self.size):
            array_new[i] = self.array[i]
        self.array = array_new
    def output(self):
        for i in range(self.size):
            print(self.array[i])

删除元素

数组的删除操作与插入操作的过程相反，如果删除的元素在中间，后面的元素都需要往前移一位。我们可以在类中添加一个remove这个方法。

    def remove(self, index):
        # 判断访问下标是否超出范围
        if index = self.size:
            raise Exception("超出数组实际元素范围！")
        # 从左到右，逐个元素向左挪动一位
        for i in range(index, self.size-1):
            self.array[i] = self.array[i+1]
        self.size -= 1

复杂度

数组扩容的时间复杂度是O(n)，插入并移动元素的时间复杂度也是O(n)，综合起来插入操作的时间复杂度就是O(n)，删除操作也只是涉及到元素的移动，时间复杂度也是O(n)。

总结

数组拥有很高的随机访问能力，给出下标就可以找到对应元素。二分查找就是利用了数组这样的优势。但是数据中的元素是紧密地存储在内存中，插入，删除数组都会引起大量元素的移动，影响效率。总而言之，数组适用于读操作多，写操作少的场景。而链表与数据正好相反，后续的文章中笔者会继续介绍python数据结构和算法。

作者：小炮哥哥

python算法 Python 数组

1024 个赞