数组

前言

数组（array）是一种线性数据结构，其将相同类型的元素存储在连续的内存空间中。我们将元素在数组中的位置称为该元素的索引（index）

特点

• 在内存中数据连续存放
• 空间效率高
• 支持随机访问。数组允许在O(1) 时间内访问任意元素
• 插入和删除效率低
• 长度不可变
• 空间容易被浪费

数组的常见操作

Python

• 初始化

arr: list[int] = [0] * 5  # [ 0, 0, 0, 0, 0 ]
nums: list[int] = [1, 3, 2, 5, 4]

# 二维数组
arr2 = [[1,2,3,4],[5,6,7,8]]

• 访问元素

def random_access(nums: list[int]) -> int:
    """随机访问元素"""
    # 在区间 [0, len(nums)-1] 中随机抽取一个数字
    random_index = random.randint(0, len(nums) - 1)
    # 获取并返回随机元素
    random_num = nums[random_index]
    return random_num

• 插入元素。数组元素在内存中是连续的，如果想在数组中间插入一个元素，则需要将该元素之后的所有元素都向后移动一位，之后再把元素赋值给该索引。按严格定义来说，数组长度是固定的，插入一个元素必定会导致数组尾部元素“丢失”

def insert(nums: list[int], num: int, index: int):
    """在数组的索引 index 处插入元素 num"""
    # 把索引 index 以及之后的所有元素向后移动一位
    for i in range(len(nums) - 1, index, -1):
        nums[i] = nums[i - 1]
    # 将 num 赋给 index 处的元素
    nums[index] = num
    
# pythonic. 追加
arr1 = [1,2,3,4]
arr1.append(5)

# 插入
arr1 = [1,2,3,4]
arr1.insert(2,9) # arr1 = [1,2,9,3,4]

• 删除元素。若想删除索引 i 处的元素，则需要把索引 i 之后的元素都向前移动一位

def remove(nums: list[int], index: int):
    """删除索引 index 处的元素"""
    # 把索引 index 之后的所有元素向前移动一位
    for i in range(index, len(nums) - 1):
        nums[i] = nums[i + 1]
        
# 删除可以用pop()、remove()、del()方法。区别在于，pop()用于移除列表中的一个元素，默认为最后一个元素，并且返回该元素的值；remove()用于一处列表中某个值的第一个匹配项；del()方法则按照索引删除元素。
arr3 = [1,2,3,1,4]
arr1.remove(1) # 删除第一个 1
arr1.pop() # 删除 4，并返回 4
del arr1[3] # 删除index为2的元素，即3

• 查找元素

# 如果只是确定数组中是否含有某一元素
arr1 = [1,2,3,4]
if 4 in arr1:
  print('yes')

# 获取元素第一次出现的索引
arr1 = [1,2,3,4]
arr1.index(3) # 2

# 基本查找方式
def find(nums: list[int], target: int) -> int:
    """在数组中查找指定元素"""
    for i in range(len(nums)):
        if nums[i] == target:
            return i
    return -1

• 修改元素

arr1 = [1,2,3,4]
arr1[1] = 9 # arr1 = [1,9,3,4]

• 反转

arr1 = [1,2,3,4]
arr1.reverse() # [4,3,2,1]

• 排序。使用sort()或者sorted()进行排序，默认升序。前者排序后直接替换，后者不保留排序结果，并没有修改原列表。

arr4 = [3,1,7,5]
arr4.sort() # [1,3,5,7]
arr4.sort(reverse=True) # [7,5,3,1]

arr5 = [2,1,4,3]
sorted(arr5) # [1,2,3,4]
sorted(arr5,reverse=True) # [4,3,2,1]
print(arr5) # [2,1,4,3]

• 清空。利用clear()方法对数组进行清空。

arr1 = [1,2,3,4]
arr1.clear() # []，空列表

• 截取。python截取列表相较于其它编程语言会简单不少，可以通过步长取数，左闭右开。

arr6 = [1,2,3,4,5,6,7,8,9]
print(arr6[1:3:1]) # [2,3]
print(arr6[0:7:2]) # 步长为2，[1,3,5,7]
print(arr6[::-2])  # 从右向左截取，步长为2。[9,7,5,3,1]
print(arr6[:-2])   # 倒数两位元素之前的所有位。[1,2,3,4,5,6,7]