数据结构（5）：数组

数组的定义

数组是由 n（n≥1）个相同类型的数据元素构成的有限序列，每个数据元素称为一个数组元素，每个元素在 n 个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界。

数组与线性表的关系：数组是线性表的推广。一维数组可视为一个线性表；二维数组可视为其元素也是定长线性表的线性表，以此类推。数组一旦被定义，其维数和维界就不再改变。因此，除结构的初始化和销毁外，数组只会有存取元素和修改元素的操作。

数组的存储结构

大多数计算机语言提供了数组数据类型，逻辑意义上的数组可采用计算机语言中的数组数据类型进行存储，一维数组的所有元素在内存中占用一段连续的存储空间。

以一维数组 A[0…n-1]为例，其存储结构关系式为

其中，L 是每个数组元素所占的存储单元。

对于多维数组，有两种映射方法：按行优先和按列优先。以二维数组为例，按行优先存储的基本思想是：先行后列，先存储行号较小的元素，行号相等先存储列号较小的元素。设二维数组行下标与列下标的范围分别为[0,h₁]与[0,h₂]，则存储结构关系式为

当以列优先方式存储时，得出存储结构关系式为

稀疏矩阵

矩阵中非零元素的个数为 t，相对矩阵元素的个数 s 来说非常少，即 s＞＞t 的矩阵称为稀疏矩阵。例如，一个矩阵的阶为 100×100，该矩阵中只有少于 100 个非零元素。

若采用常规的办法存储稀疏矩阵，则相当浪费存储空间，因此仅存储非零元素。但通常零元素的分布没有规律，所以仅存储非零元素的值是不够的，还要存储它所在的行和列。因此，将非零元素及其相应的行和列构成一个三元组（行标，列标，值）。然后再按某种规律存储这些三元组。稀疏矩阵压缩存储后便失去了随机存取特性。

稀疏矩阵的三元组即可以采用数组存储，也可以采用十字链表法存储。

数组的应用

关于数组的定义就说到这里，查找元素和修改元素的操作非常的简单，我就直接跳过。我们直接来看到数组的应用！这里我选择两个比较简单的应用：有效的数独以及旋转图像。

有效的数独

判断一个 9×9 的数独是否有效，只需要根据以下规则，验证已填入的数字是否有效即可。

1. 数字 1-9 在每一行只能出现一次；
2. 数字 1-9 在每一列只能出现一次；
3. 数字 1-9 在每一个以粗实线分隔的 3×3 宫内只能出现一次。

上图是一个部分填充的有效数独。

数独部分空格内已填入数字，空白格用'.'表示。

说明：

• 一个有效的数独（部分已被填充）不一定是可解的。
• 只需根据以上的规则，验证已填入的数字是否有效即可。
• 给定数独序列只包含数字 1-9 和字符'.'。
• 给定数独永远是 9×9 形式的。

思路

一个简单的解决方案是遍历该 9×9 数独三次，以确保：

• 行中没有重复的数字。
• 列中没有重复的数字。
• 3×3 子数独内没有重复的数字。

实际上，所有这一切都可以在一次迭代中完成。

方法：一次迭代

首先，让我们来讨论下面两个问题：

• 如何枚举子数独？

可以使用 box_index=row//3*3+columns//3。

• 如何确保行/列/子数独中没有重复项？

可以利用 value->count 哈希映射来跟踪所有已遇到的值。

现在，我们完成了这个算法的所有准备工作：

• 遍历数独。
• 检查每个单元格值是否已经在当前的行/列/子数独中出现过：如果出现重复，返回 False。如果没有，则保留此值以进行进一步跟踪。
• 返回 True。

算法的实现如下：

class Solution:
    # noinspection PyMethodMayBeStatic
    def is_valid_sudoku(self, board: List[List[str]]) -> bool:
        # init data
        rows, columns, boxes = [{}for _ in range(9)], [{}for _ in range(9)], [{}for _ in range(9)]
        # validate a board
        for i in range(9):
            for j in range(9):
                num = board[i][j]
                if num != '.':
                    num, box_index = int(num), i//3*3+j//3
                    # keep the current cell value
                    rows[i][num], columns[j][num], boxes[box_index][num] = rows[i].get(num, 0)+1, columns[j].get(
                        num, 0)+1, boxes[box_index].get(num, 0)+1
                    # check if this value has been already seen before
                    if rows[i][num] > 1 or columns[j][num] > 1 or boxes[box_index][num] > 1:
                        return False
        return True

旋转图像

给定一个 n×n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

提示：

• matrix.length=n
• matrix[i].length=n
• 1≤n≤20
• -1000≤matrix[i][j]≤1000

方法一：使用辅助数组

我们分析将图像旋转 90 度之后，这些数字出现在什么位置。

对于矩阵中的第一行而言，在旋转后，它出现在倒数第一列的位置。

并且，第一行的第 x 个元素在旋转后恰好是倒数第一列的第 x 个元素。

对于矩阵的第二行而言，在旋转后，它出现在倒数第二列的位置。

对于矩阵的第三行和第四行同理。这样我们可以得到规律：

对于矩阵中的第 i 行的第 j 个元素，在旋转后，它出现在倒数第 i 列的第 j 个位置。

我们将其翻译成代码。由于矩阵中的行列从 0 开始计数，因此对于矩阵中的元素 matrix[row][col]，在旋转后，它的新位置为 matrix_new[col][n-row-1]。

这样以来，我们使用一个与 matrix 大小相同的辅助数组 matrix_new，临时存储旋转后的结果，我们遍历 matrix 中的每一个元素，根据上述规则将该元素存放到 matrix_new 中对应的位置。在遍历完成之后，再将 matrix_new 中的结果复制到原数组中即可。

算法的实现如下：

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        # Python 这里不能 matrix_new = matrix 或 matrix_new = 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
        matrix[:] = matrix_new

复杂度分析

• 时间复杂度 O(N²)，其中 N 是 matrix 的边长。
• 空间复杂度 O(N²)。我们需要使用一个和 matrix 大小相同的辅助数组。

方法二：原地旋转

题目中要求我们尝试不使用额外内存空间的情况下进行矩阵的旋转，也就是说，我们需要“原地旋转”这个矩阵。那么我们如何在方法一的基础上完成原地旋转呢？

我们观察方法一中的关键等式：

matrix_new[col][n-row-1]=matrix[row][col]

它阻止了我们进行原地旋转，这是因为如果我们直接将 matrix[row][col] 放到原矩阵的目标位置 matrix[col][n-row-1]：

matrix[col][n-row-1]=matrix[row][col]

原矩阵中的 matrix[col][n-row-1] 就被覆盖了！这并不是我们想要的结果。因此我们可以考虑用一个临时变量 temp 暂存 matrix[col][n-row-1]的值，这样虽然 matrix[col][n-row-1]被覆盖了，我们还是可以通过 temp 获取它原来的值。

那么 matrix[col][n-row-1]经过旋转之后会到哪个位置呢？我们还是使用方法一中的关键等式，不过这次，我们需要将

代入关键等式，就可以得到

matrix[n-row-1][n-col-1]=matrix[col][n-row-1]

同样的，直接赋值会覆盖掉 matrix[n-row-1][n-col-1]原来的值，因此我们还是需要使用一个临时变量进行存储，不过这次，我们可以直接使用之前的临时变量 temp。

我们再重复一次之前的操作 matrix[n-row-1][n-col-1]经过旋转操作之后会到哪个位置呢？

代入关键等式，就可以得到：

matrix[n-col-1][row]=matrix[n-row-1][n-col-1]

写进去：

不要灰心，再来一次！matrix[n-col-1][row]经过旋转操作之后回到哪个位置呢？

代入关键等式，就可以得到：

matrix[row][col]=matrix[n-col-1][row]

我们回到了最初的起点，也就是说：

这四项处于一个循环中，并且每一项旋转后的位置就是下一项所在的位置！因此我们可以使用一个临时变量 temp 完成这四项的原地交换。

当我们知道了如何原地旋转矩阵之后，还有一个重要的问题在于：我们应该枚举哪些位置（row，col）进行上述的原地交换操作呢？由于每一次原地交换四个位置，因此：

• 当 n 为偶数时，我们需要枚举 n²/4=(n/2)×(n/2)个位置，可以将图形分成四块，保证了不重复、不遗漏。
• 当 n 为奇数时，由于中心的位置经过旋转后位置不变，我们需要枚举(n²-1)/4=((n-1)/2)×((n+1)/2)个位置，需要换一种划分方式，同样保证了不重复、不遗漏，矩阵正中央的点无需旋转。

算法的实现如下：

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        for i in range(n//2):
            for j in range((n+1)//2):
                matrix[i][j], matrix[n-j-1][i], matrix[n-i-1][n-j-1], matrix[j][n-i-1] =\
                    matrix[n-j-1][i], matrix[n-i-1][n-j-1], matrix[j][n-i-1], matrix[i][j]

复杂度分析

• 时间复杂度：O(N²)，其中 N 为 matrix 的边长。我们需要枚举的子矩阵大小为

• 空间复杂度为：O(1)。为原地旋转。

方法三：用翻转代替旋转

我们还可以另辟蹊径，用翻转操作代替旋转操作。先通过水平轴翻转，再根据主对角线翻转，就得到了答案。这是为什么呢？对于水平轴翻转而言，我们只需要枚举矩阵上半部分的元素，和下半部分的元素进行交换，即

matrix[row][col]=matrix[n-row-1][col]

对于主对角线翻转而言，我们只需枚举对角线左侧的元素，和右侧的元素进行交换，即：

matrix[row][col]=matrix[col][row]

将它们联立即可得到：

matrix[row][col]=matrix[col][n-row-1]

和方法一、方法二中的关键等式：

matrix_new[col][n-row-1]=matrix[row][col]

是一致的。

算法的实现如下：

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        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]

复杂度分析

• 时间复杂度：O(N²)，其中 N 是 matrix 的边长。对于每一次翻转操作，我们都需要枚举矩阵中一半的元素。
• 空间复杂度：O(1)。为原地翻转得到的原地旋转。

总结

关于数组及其应用就说到这里，下一回我们来看一种非常特殊的线性结构：串！

当然，我从今年开始已经入驻 B 站了！下面给出 B 站账号：新时代的运筹帷幄，喜欢的可以关注一下，看完视频不要忘记一键三连啊！