数据结构与算法实例详解--矩阵、数组篇

数组

定义：数组是一种线性数据结构，用于存储相同类型的一组元素。数组中的每个元素可以通过索引来访问。

特点：

1. 固定大小：数组的大小在创建时确定，一旦分配，无法更改。
2. 随机访问：可以通过索引以常量时间 $O(1)$ 访问任意元素。
3. 存储连续：数组元素在内存中是连续存储的，这使得数据访问效率较高。

用途：

• 存储一组数据（如整数、浮点数等）的集合。
• 实现其他数据结构（如栈、队列等）。
• 在算法中用于排序、查找等操作。

矩阵

定义：矩阵是一个以矩形形式排列的数值集合，通常被表示为二维数组。矩阵可以看作是数组的扩展，特别是高维数据的表示。

特点：

1. 二维结构：矩阵包含行和列，能够表示复杂的数据关系。
2. 元素访问：可以通过行和列的索引访问元素，访问时间通常也是 $O(1)$。
3. 存储复杂数据：适合表示图形、图像和网络等复杂结构。

用途：

• 数学计算（如线性代数），矩阵运算（加法、乘法、转置等）。
• 图形学中表示像素数据。
• 机器学习中的数据集表示，尤其是特征向量和标签的存储。

总结

数组和矩阵都是用于数据存储的重要工具。数组适用于简单的线性数据存储，而矩阵则能够处理更复杂的多维数据关系。在算法的设计和实现中，选择适合的数据结构对于提高效率和简化代码具有重要意义。

话不多说，直接看题：

题目描述：

给你一个二维 二进制 数组 grid。请你找出一个边在水平方向和竖直方向上、面积 最小 的矩形，并且满足 grid 中所有的 1 都在矩形的内部。

返回这个矩形可能的 最小 面积。

示例 1：

输入： grid = [[0,1,0],[1,0,1]]

输出： 6

解释：​

这个最小矩形的高度为 2，宽度为 3，因此面积为 2 * 3 = 6 

示例 2：

输入： grid = [[0,0],[1,0]]

输出： 1

解释：

​​

这个最小矩形的高度和宽度都是 1，因此面积为 1 * 1 = 1。

提示：

• 1 <= grid.length, grid[i].length <= 1000
• grid[i][j] 是 0 或 1。
• 输入保证 grid 中至少有一个 1 。

题目分析：

        求矩形面积，也就是在找最左边的1的列号firstCol，最右边的1列号lastCol,最上面1的行号firstRow,最下面1的行号lastRow。

        那么面积就是  (lastRow-firstRow+1)*(lastCol-firstCol+1)

        遍历矩阵，分别找第一列，最后一列，第一行，最后一行出现1的数据，然后计算求结果。

代码实现：

​

class Solution:
    def minimumArea(self, grid: List[List[int]]) -> int:
        rowNums = len(grid)
        colNums = len(grid[0])
        firstRow = -1
        firstCol = -1
        lastRow = -1
        lastCol = -1
        for row in range(rowNums):
            if firstRow==-1:
                for col in range(colNums):
                    if grid[row][col]==1:
                        if firstRow==-1:
                            firstRow=row
                            break

        for col in range(colNums):
            if firstCol==-1:
                for row in range(rowNums):
                    if grid[row][col]==1:
                        if firstCol==-1:
                            firstCol=col
                            break

        for row in range(rowNums-1,-1,-1):
            if lastRow==-1:
                for col in range(colNums-1,-1,-1):
                    if grid[row][col]==1:
                        if lastRow==-1:
                            lastRow=row
                            break

        for col in range(colNums-1,-1,-1):
            if lastCol==-1:
                for row in range(rowNums-1,-1,-1):
                    if grid[row][col]==1:
                        if lastCol==-1:
                            lastCol=col
                            break

        value = (lastRow-firstRow+1)*(lastCol-firstCol+1)
        return value

总结：

详解：

1. 首先，定义了网格的行数 rowNums 和列数 colNums 。
2. 然后，通过四个循环分别找到值为 1 的单元格首次出现的行 firstRow 和列 firstCol ，以及最后出现的行 lastRow 和列 lastCol 。
   • 在第一个循环中，从第一行开始逐行查找，当找到第一个值为 1 的单元格时，记录其所在的行 firstRow ，并结束内层循环。
   • 第二个循环类似，从第一列开始逐列查找，记录第一个值为 1 的单元格所在的列 firstCol 。
   • 第三个循环从最后一行开始逐行向前查找，记录最后一个值为 1 的单元格所在的行 lastRow 。
   • 第四个循环从最后一列开始逐列向前查找，记录最后一个值为 1 的单元格所在的列 lastCol 。
3. 最后，根据找到的边界计算最小矩形区域的面积 value ，公式为 (lastRow - firstRow + 1) * (lastCol - firstCol + 1) 。

考点：

1. 对二维数组的遍历和操作。
2. 循环的使用和条件判断。
3. 如何确定一个区域的边界。

收获：

1. 加深对二维数组操作的理解，包括如何遍历和根据特定条件获取相关信息。
2. 学会通过多个循环和条件判断来确定一个区域的边界，并计算其相关属性（如面积）。
3. 提高在解决实际问题时，对问题进行分析和转化为代码实现的能力。