数组

基本概念

一种线性表数据结构，利用一段连续的内存空间，存储一组相同类型的数据。

数据结构的三要素

• 逻辑结构
  • 线性结构
• 存储结构
  • 顺序存储
• 数据的运算

费曼理解

就是现实生活用到的表格，地址固定、支持随机访问
下标 ii 的元素地址 = 首地址 + ii × 单个元素占用的字节数

内部实现：

int arr[size]={}

复杂度分析：

元素访问

def get_element(nums:list[int],index:int):
	#边界判定
	if 0<= index<=len(nums):
		return nums[index]
	else:
		raise IndexError(f"index超出数组范围")

复杂度分析

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

元素查找

def find_element(nums:list[int],val:int):
	for i in range(len(nums)):
		if nums[i]==val:
			return i
	return false

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

元素插入

def insert_element(nums:list[int],index:int,val:int):
	if 0<=index<=len(nums):
		nums.append(0)
		for i in range(len(nums)-1,indix,-1):
			nums[i]=nums[i-1]
		nums[i]=val
		return true
	else:
		return false

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

改变元素

def change_element(nums:list[int],index:int,val:int):
	if 0<=index<=len(nums):
		nums[index]=val
		return true
	else:
		return false

复杂度分析

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

删除元素

def delete_element(nums:list[int],index:int):
	if 0<=index<=len(nums):
		for i in range(index,len(nums)-1):
			nums[i]=nums[i+1]
		nums.pop()
		return true
	else:
		return false

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

应用场景：

数组基础

• 移动零
  • 问题描述：将所有0移动到数组后面且不改变数组相对顺序
  • 解决方案：不断将元素0和非0元素交换位置
• 杨辉三角
  • 问题描述：返回n+1行的杨辉三角
  • 解决方案：模拟杨辉三角的运算即可
• 甲板上的战舰
  • 问题描述：找到舰队数量
  • 解决方案：观察舰队特征，遍历统计即可
• 区间加法II
  • 问题描述：返回最大值数量
  • 解决方案：找到重叠区域的长和宽即可，面积就是数量
• 189 轮转数组
  • 问题描述：给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数
  • 解决方案：三次反转
• 54 螺旋矩阵
  • 问题描述： 顺时针螺旋顺序 ，返回矩阵中的所有元素。
  • 解决方案：通过四个方向的顺序遍历并不断更新四个角的坐标即可
• 66加一
  • 问题描述：将大整数加 1，并返回结果的数字数组。
  • 解决方案一：反向遍历，判断当前数字是否是10
  • 解决方案二：反向便利，判断是否需要进位
• 724寻找数组的中心下标
  • 问题描述：计算数组的 中心下标
  • 解决方案：遍历判断符合条件即可
• 498对角线遍历
  • 问题描述：对角线遍历
  • 解决方案：记录遍历方向，越界反转