前言
Datawhale组队学习丨9月Leetcode算法入门与数组丨打卡笔记
这篇博客是一个 入门型 的文章，主要是自己学习的一个记录。
内容会参考这篇笔记（很详细）：LeetCode 算法笔记（Leetcode-Notes）
1 数组简介
数组定义
数组（Array）：一种线性表数据结构。它使用一组连续的内存空间，来存储一组具有相同类型的数据，是实现线性表的顺序结构存储的基础。
- 线性表：相同类型的数据元素排成线一样的结构，每个元素最多有前、后两个方向。数**组、栈、队列、链表 **都是线性表结构。
- 连续的内存空间：线性表中顺序存储结构，占用的内存空间连续，也就是说相邻数据元素之间，物理内存上的存储位置相邻。
随机访问数据元素
数组可以根据下标，直接随机指定到某一个元素存放的位置进行访问，也就是说数组具有随机访问的特点。
在定义数组的时候，首先计算机会给数组分配一组连续的存储空间，其中第一个元素的地址称为首地址，之后的元素都具有下标索引和内存地址。计算机通过地址来访问数据元素，并通过寻址公式计算出对应元素的内存地址。
寻址公式
下标
i
对应的数据元素地址
=
数组首地址
+
i
×
单个数据元素所占内存大小
下标 i 对应的数据元素地址 = 数组首地址 + i \times 单个数据元素所占内存大小
下标i对应的数据元素地址=数组首地址+i×单个数据元素所占内存大小
多维数组
上面介绍的数组只有一个维度，是一维数组，其数据元素也是单下标索引。
在实际生活中，经常会遇到二维或者多为的数据，那么这些数据的存储可能就会用到多维数组。例如二维数组，可以看作是一个特殊的一维数组，即一维数组中的元素也是一个数组。
不同编程语言中数组的实现
不同编程语言中数组的实现可能会有所不同，以下是几种常见编程语言中数组的实现方式：
-
C语言：C语言中的数组是一组相同类型的连续内存空间。可以通过声明数组变量并指定大小来创建数组，例如： int arr[5]; 。数组元素可以通过索引访问，索引从0开始，例如： arr[0] = 10; 。
-
Java：Java中的数组也是一组相同类型的连续内存空间。可以通过声明数组变量并使用 new 关键字来创建数组，例如： int[] arr = new int[5]; 。数组元素同样可以通过索引访问，例如： arr[0] = 10; 。
-
Python：Python中的数组可以使用列表（List）来实现。列表可以包含不同类型的元素，并且可以动态调整大小。可以使用方括号创建列表，例如： arr = [1, 2, 3, 4, 5] 。可以通过索引访问和修改列表元素，例如： arr[0] = 10 。
-
JavaScript：JavaScript中的数组也可以使用方括号创建，例如： var arr = [1, 2, 3, 4, 5]; 。与Python类似，JavaScript数组可以包含不同类型的元素，并且可以动态调整大小。可以通过索引访问和修改数组元素，例如： arr[0] = 10; 。
2 数组的基本操作
增、删、改、查 基本上涉及这四种操作。
2.1 访问元素
访问数组中第 i i i 个元素：
- 检查 i i i 的范围是否在合法的区间内，即 0 ≤ i ≤ l e n ( n u m s ) − 1 0\le i \le len(nums)-1 0≤i≤len(nums)−1 。超出范围内的访问为非法访问。
- 如果是合法访问，则由给定下标得到元素值。
# 从数组 nums 中读取下标为 i 的数据元素值
def value(nums, i):
if 0 <= i <= len(nums) - 1:
print(nums[i])
arr = [0, 5, 2, 3, 7, 1, 6]
value(arr, 3)
2.2 查找元素
查找数组中元素值为 v a l val val 的位置：
- 建立一个基于下标的循环，每次将 v a l val val 与当前数据元素 n u m s [ i ] nums[i] nums[i] 进行比较。
- 在找到元素的时候返回元素下标。
- 遍历完找不到时可以返回一个特殊值（例如 −1）。
# 从数组 nums 中查找元素值为 val 的数据元素第一次出现的位置
def find(nums, val):
for i in range(len(nums)):
if nums[i] == val:
return i
return -1
arr = [0, 5, 2, 3, 7, 1, 6]
print(find(arr, 5))
2.3 插入元素
添加元素到列表末尾：
arr = [1, 2, 3, 4, 5]
arr.append(6)
print(arr) # 输出：[10, 2, 3, 4, 5, 6]
插入元素到指定位置：
arr = [1, 2, 3, 4, 5]
arr.insert(2, 7) # 在索引为2的位置插入元素7
print(arr) # 输出：[10, 2, 7, 3, 4, 5, 6]
2.4 改变元素
将元素中第 i i i 个元素值改为 v a l val val ：
- 检查 i i i 的范围是否在合法的区间内，即 0 ≤ i ≤ l e n ( n u m s ) − 1 0\le i \le len(nums)-1 0≤i≤len(nums)−1 。超出范围内的访问为非法访问。
- 如果是合法访问，则将第 i i i 个元素值赋值为 v a l val val。
def change(nums, i, val):
if 0 <= i <= len(nums) - 1:
nums[i] = val
arr = [0, 5, 2, 3, 7, 1, 6]
i, val = 2, 4
change(arr, i, val)
print(arr)
2.5 删除元素
Python中删除数组元素的几种常见方法：
- 删除数组尾部元素：
arr = [1, 2, 3, 4, 5]
arr.pop() # 删除并返回最后一个元素
print(arr) # 输出：[1, 2, 3, 4]
- 删除数组指定位置上的元素：（首先要检查下标是否合法，合法之后再进行之后操作）
arr = [1, 2, 3, 4, 5]
arr.pop(2) # 删除索引为2的元素
print(arr) # 输出：[1, 2, 4, 5]
- 基于条件删除元素：
arr = [1, 2, 3, 4, 5]
arr.remove(3) # 删除所有等于3的元素
print(arr) # 输出：[1, 2, 4, 5]
3 总结
数组作为最基本的顺序结构存储方式，支持随机访问。在执行增删改查操作时，不同的操作对于时间复杂度的影响也不同。
当涉及到数组的增删改查操作时，不同操作的时间复杂度会有所不同。以下是一些示例：
- 访问元素（随机访问）：
- 时间复杂度：O(1)
- 无论数组多大，通过索引直接访问元素的时间是恒定的，因为数组元素在内存中是连续存储的。例如，访问数组中的第一个元素或最后一个元素都只需要一步操作。
- 插入元素：
-
在数组的末尾插入元素：
- 时间复杂度：O(1)
- 当在数组末尾插入元素时，只需要将元素添加到数组的最后一个位置。
-
在数组的其他位置插入元素：
- 时间复杂度：O(n)
- 当在数组的其他位置插入元素时，需要将插入位置后面的所有元素向后移动一位，以腾出空间插入新元素。
- 删除元素：
-
删除数组末尾的元素：
- 时间复杂度：O(1)
- 当删除数组末尾的元素时，只需要将数组的长度减一即可。
-
删除数组的其他位置的元素：
- 时间复杂度：O(n)
- 当删除数组的其他位置的元素时，需要将删除位置后面的所有元素向前移动一位，以填补删除的空缺。
- 修改元素：
- 时间复杂度：O(1)
- 通过索引直接访问并修改数组中的元素，时间复杂度为常数。
task03
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
digits = [0] + digits
digits[len(digits)-1] += 1
for i in range(len(digits)-1, 0, -1):
if digits[i] != 10:
break
else:
digits[i] = 0
digits[i-1] += 1
if digits[0] == 0:
return digits[1:]
else:
return digits
class Solution:
def pivotIndex(self, nums: List[int]) -> int:
sum = 0
for i in range(len(nums)):
sum += nums[i]
sum_t = 0
for i in range(len(nums)):
if sum_t * 2 + nums[i] == sum:
return i
sum_t += nums[i]
return -1
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
k = k % n
self.reverse(nums, 0, n-1)
self.reverse(nums, 0, k-1)
self.reverse(nums, k, n-1)
def reverse(self, nums: List[int], left: int, right: int) ->None:
while left < right :
temp = nums[left]
nums[left] = nums[right]
nums[right] = temp
left += 1
right -= 1
task04
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
matrix_new = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
matrix_new[j][n-i-1] = matrix[i][j]
matrix[:] = matrix_new
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix: return []
l, r, t, b, res = 0, len(matrix[0]) - 1, 0, len(matrix) - 1, []
while True:
for i in range(l, r+1): res.append(matrix[t][i])
t += 1
if t > b : break
for i in range(t, b+1): res.append(matrix[i][r])
r -= 1
if l > r: break
for i in range(r, l-1, -1): res.append(matrix[b][i])
b -= 1
if t > b: break
for i in range(b, t-1, -1): res.append(matrix[i][l])
l += 1
if l > r: break
return res
class Solution:
def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
x, y, m, n, ans = 0, 0, len(mat), len(mat[0]), []
for j in range(m*n):
ans.append(mat[x][y])
if (x + y) % 2 == 0: # 右上方移动
if y == n-1:
x += 1 # 第一行
elif x == 0:
y += 1 # 最后一列
else:
x -= 1
y += 1
else:
if x == m-1:
y += 1 # 最后一行
elif y == 0:
x += 1 # 第一列
else:
x += 1
y -= 1
return ans
参考文献
- [1] https://datawhalechina.github.io/leetcode-notes/#/
—— END ——
如果以上内容有任何错误或者不准确的地方，欢迎在下面 👇 留言。或者你有更好的想法，欢迎一起交流学习~~~
更多精彩内容请前往 AXYZdong的博客
