查询网格图中每一列的宽度

标签: 数组 矩阵

难度: Easy

给你一个下标从 0 开始的 m x n 整数矩阵 grid 。矩阵中某一列的宽度是这一列数字的最大 字符串长度 。

  • 比方说，如果 grid = [[-10], [3], [12]] ，那么唯一一列的宽度是 3 ，因为 -10 的字符串长度为 3 。

请你返回一个大小为 n 的整数数组 ans ，其中 ans[i] 是第 i 列的宽度。

一个有 len 个数位的整数 x ，如果是非负数，那么 字符串长度 为 len ，否则为 len + 1 。

示例 1：

输入：grid = [[1],[22],[333]]
输出：[3]
解释：第 0 列中，333 字符串长度为 3 。

示例 2：

输入：grid = [[-15,1,3],[15,7,12],[5,6,-2]]
输出：[3,1,2]
解释：
第 0 列中，只有 -15 字符串长度为 3 。
第 1 列中，所有整数的字符串长度都是 1 。
第 2 列中，12 和 -2 的字符串长度都为 2 。

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 100
  • -109 <= grid[r][c] <= 109

Submission

运行时间: 31 ms

内存: 17.3 MB

class Solution:
    def findColumnWidth(self, grid: List[List[int]]) -> List[int]:
        m = len(grid)
        n = len(grid[0])
        result = []
        for j in range(n):
            tmp = 0
            for i in range(m):
                tmp = max(tmp, len(str(grid[i][j])))
            result.append(tmp)
        return result

Explain

此题解通过遍历矩阵中的每一列，对于每列中的每个元素，将其转换为字符串并计算字符串的长度。通过在内部循环中维护一个变量tmp，记录当前列中最大的字符串长度。最后，将每列的最大长度存储到结果列表中并返回。

时间复杂度: O(m*n)

空间复杂度: O(n)

class Solution:
    def findColumnWidth(self, grid: List[List[int]]) -> List[int]:
        m = len(grid)  # 矩阵的行数
        n = len(grid[0])  # 矩阵的列数
        result = []  # 结果列表，用于存储每列的最大宽度
        for j in range(n):  # 遍历每一列
            tmp = 0  # 初始化当前列的最大宽度
            for i in range(m):  # 遍历当前列的每一个元素
                tmp = max(tmp, len(str(grid[i][j])))  # 更新当前列的最大宽度
            result.append(tmp)  # 将当前列的最大宽度加入结果列表
        return result  # 返回结果列表

Explore

在题解中不使用`str(abs(grid[i][j]))`来忽略负号，是因为在计算列宽度时，负号是整个数字表示的一部分，应被考虑在内。如果列中包含负数，负号也会占用字符空间，从而影响宽度的计算。正确反映每个元素的实际宽度可以确保列宽度足够以展示所有元素，包括负号。

确实，题解中未说明如何处理空矩阵或空行的情况。理想的解决方案应该包括对这些边缘情况的检查。例如，可以在函数开始时添加一段代码来检查`grid`是否为空或首行是否为空，如果是，则直接返回一个空列表。这样可以避免运行时错误，并确保函数在任何输入下都能稳定运行。

当前算法已经是在不改变数据输入结构的情况下，针对问题的直接解法。由于需要确定每一列的最大宽度，我们必须检查该列的每个元素，因此每个元素至少被访问一次。在这种情况下，算法的时间复杂度基本上是最优的。如果矩阵的存储或访问方式有更高效的结构（例如，如果数据以列为主的格式存储），可能会进一步优化访问速度，但这超出了常规二维数组的处理范畴。

在实际应用中，确实应当考虑到矩阵的尺寸，因为极大的数据输入会导致显著的性能下降，特别是在内存使用和处理时间上。在实现算法时，可以设定一些合理的限制，如矩阵的最大行数和列数，以确保程序可以在合理的时间内完成运算。这种做法可以在文档中明确说明，或者在代码中通过异常处理来实施，以便于用户理解可能的性能风险。