[数据结构与算法]数组基本知识

0. 内容说明

最近在自己编写一些小的算法的时候，深感自己的算法过于臃肿。碰巧Datawhale在新的一期组队学习中组织了数据结构与算法的课程学习。于是就参加了，再次感谢Datawhale~~

首先跟大家分享一下两个自己感觉比较好的学习资料，一个是 算法通关手册 ，也是Datawhale在本次组队学习中的学习资料；一个是B站上的视频 【北京大学】数据结构与算法Python版（完整版），老师讲的特别棒（也难得有Python版的数据结构课程，哈哈~）。

需要指出的是：本次博客的内容更像是对上述两个资料做的笔记，很多都是资料上的原内容，并非原创。

1. 数组的基本定义

数组是存放在连续内存空间上的相同类型数据的集合。数组可以方便的通过下标索引的方式获取到下标下对应的数据。（图片来自于资料 算法通关手册）

数组的两大特点：线性表 和 连续的内存空间 。

• 线性表：线性表就是所有数据元素排成像一条线一样的结构，线性表上的数据元素都是相同类型，且每个数据元素最多只有前、后两个方向。
• 连续的内存空间：线性表有两种存储结构：「顺序存储结构」和「链式存储结构」（在上一篇blog 数据结构与算法简介 中有介绍）。其中，「顺序存储结构」是指占用的内存空间是连续的，相邻数据元素之间，物理内存上的存储位置也相邻。数组也是采用了顺序存储结构，并且存储的数据都是相同类型的。

综合这两个角度，数组就可以看做是：使用了「顺序存储结构」的「线性表」的一种实现方式。

2. 数组的基本操作

数组的基本操作就是我们最常提到的那四个字：增、删、改、查

2.1 增

增加元素分为两类：【在数组的尾部增加元素】以及【在数组的第 i 位增加元素】。

• 在数组的尾部增加元素：在数组的尾部增加元素较为简单，只需要开辟一个新的内存空间并将数据插入即可，算法复杂度为 $O(1)$。

在python中，我们可以使用 append 这个函数来实现上述操作

arr = [0, 5, 2, 3, 7, 1, 6]
val = 4
arr.append(val)

• 在数组的第 i 位增加元素
  先检查插入下标 i 是否合法，即 0 <= i <= len(nums)。确定合法位置后，通常情况下第 i 个位置上已经有数据了（除非 i == len(nums) ），要把第 i 个位置到第 len(nums) - 1 位置上的元素依次向后移动，然后再在第 i 个元素位置插入 val 值，并更新数组的元素计数值。因为移动元素的操作次数跟元素个数有关，最坏和平均时间复杂度都是 $O(n)$
  
  Python 中的 list 直接封装了中间插入操作，直接调用 insert 方法即可

arr = [0, 5, 2, 3, 7, 1, 6]
i, val = 2, 4
arr.insert(i, val)

2.2 删

增加元素分为两类：【在数组的尾部删除元素】以及【在数组的第 i 位删除元素】。

• 在数组的尾部删除元素：
  只需将元素计数值减一即可。这样原来的数组尾部元素不再位于合法的数组下标范围，就相当于删除了。时间复杂度为 $O(1)$
  
  Python 中的 list 直接封装了删除数组尾部元素的操作，只需要调用 pop 方法即可。

arr = [0, 5, 2, 3, 7, 1, 6]
arr.pop()

• 在数组的第 i 位删除元素：
  先检查下标 i 是否合法，即 o <= i <= len(nums) - 1。如果下标合法，则将第 i + 1 个位置到第 len(nums) - 1 位置上的元素依次向左移动。删除后修改数组的元素计数值。删除中间位置元素的操作同样涉及移动元素，而移动元素的操作次数跟元素个数有关，因此删除中间元素的最坏和平均时间复杂度都是$O(n)$
  
  Python 中的 list 直接封装了删除数组中间元素的操作，只需要以下标作为参数调用 pop 方法即可

arr = [0, 5, 2, 3, 7, 1, 6]
i = 3
arr.pop(i)

2.3 改

将数组中第 i 个元素值改为 val：改变元素操作跟访问元素操作类似。需要先检查 i 的范围是否在合法的范围区间，即 0 <= i <= len(nums) - 1。然后将第 i 个元素值赋值为 val。访问操作不依赖于数组中元素个数，因此时间复杂度为 $O(1)$

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)

2.4 查

查找数组中元素值为 val 的位置：在数组无序的情况下，只能通过将 val 与数组中的数据元素逐一对比的方式进行检索，也称为线性查找。建立一个基于下标的循环，每次将val 与当前数据元素 nums[i] 进行比较。在找到元素的时候返回元素下标，找不到时可以返回一个特殊值（例如 -1）。线性查找操作依赖于数组中元素个数，因此时间复杂度为 $O(n)$

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]

3. 数组基本题目

需要指出的是，以下答案是我参考或者直接借鉴 算法通关手册 一书中给出的答案，大家可以去该资料中查看相应题目更详细的解答和讲解

3.1 0066加一：

题目描述：

解答：

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        size = len(digits)
        digits[size-1] += 1
        digits = [0]+digits
        for i in range(size,0,-1):
            if digits[i] == 10:
                digits[i] = 0
                digits[i-1] += 1
        if digits[0] == 0:
                result = digits[1:]
        else:
            result = digits
        return result

3.2 0724 寻找数组中心下标

题目描述：

解答：

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        size = len(nums)
        sum = 0
        for i in range(size):
            sum += nums[i]
        cum_sum = 0
        for i in range(size):
            if cum_sum*2 + nums[i] == sum:
                return i
            cum_sum += nums[i]
        return -1

3.3 0189旋转数组

题目描述：（注意题目中提到希望我们可以在空间复杂度为 $O(1)$ 的情况下解答，即就在原数组上进行操作）

解答：

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        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 :
            tmp = nums[left]
            nums[left] = nums[right]
            nums[right] = tmp
            left += 1
            right -= 1

3.4 0048. 旋转图像

题目描述：

解答：

def rotate(self, matrix: List[List[int]]) -> None:
    n = len(matrix)
    for i in range(n//2):
        for j in range(n):
            matrix[i][j], matrix[n-i-1][j] = matrix[n-i-1][j], matrix[i][j]
    for i in range(n):
        for j in range(i):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

3.5 0054. 螺旋矩阵

题目描述：

解答：

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        up, down, left, right = 0, len(matrix)-1, 0, len(matrix[0])-1
        ans = []
        while True:
            for i in range(left, right + 1):
                ans.append(matrix[up][i])
            up += 1
            if up > down:
                break
            for i in range(up, down + 1):
                ans.append(matrix[i][right])
            right -= 1
            if right < left:
                break
            for i in range(right, left - 1, -1):
                ans.append(matrix[down][i])
            down -= 1
            if down < up:
                break
            for i in range(down, up - 1, -1):
                ans.append(matrix[i][left])
            left += 1
            if left > right:
                break
        return ans