Python中的矩阵模式挑战

[QPY课程团队]

矩阵可以隐藏出令人惊讶的优雅模式——尤其是当它们与递归思维和高效算法结合时。在这篇文章中，我们将探讨两个有趣的矩阵问题，这些问题将考验你的逻辑思维，并帮助你掌握矩阵遍历技术！

---

问题一：计算小于目标值的元素个数

问题

给定一个矩阵，其中：

• 每一行都是升序排列
• 每一列也都是升序排列

你的任务是？编写一个函数，计算有多少元素小于给定的目标值。没错——你需要在O(n + m)的时间复杂度内完成这个任务。

策略

• 从右上角开始。
• 如果当前值小于目标值，那么该行左侧的所有元素也都小于目标值。因此，计算它们的数量并向下方移动。
• 如果当前值大于或等于目标值，则向左侧移动以寻找更小的数字。
• 继续这样做，直到你脱离矩阵。

Python 解决方案

def count_less_than(matrix, target):
    if not matrix or not matrix[0]:
        return 0

    n = len(matrix)
    m = len(matrix[0])
    count = 0

    row = 0
    col = m - 1

while row < n and col >= 0:
        if matrix[row][col] < target:
            count += (col + 1)
            row += 1
        else:
            col -= 1

    return count

测试一下！

matrix = [
    [1, 2, 3, 4],
    [2, 3, 4, 5],
    [3, 4, 5, 6],
    [4, 5, 6, 7]
]

print(count_less_than(matrix, 5))  # 输出: 10

这段代码统计了所有小于 5的值，结果为 10。

---

问题二：次对角线的最小值和最大值

问题

给定一个 方阵，找出 次对角线 上的 最小值和最大值，次对角线从 右上角到左下角。

示例:

次对角线
→       3
    →   6
        → 9

策略

• 如果矩阵为空，返回 [None, None]。
• 对于每个 i 从 0 到 n-1，次对角线元素位于索引 [i][n - 1 - i]。
• 在遍历过程中跟踪 最小值 和 最大值。




Python解决方案

def solution(grid):
    if not grid:
        return [None, None]

    n = len(grid)
    if n == 0:
        return [None, None]

    min_value = float('inf')
    max_value = float('-inf')

for i in range(n):
        secondary_diagonal_value = grid[i][n - 1 - i]
        min_value = min(min_value, secondary_diagonal_value)
        max_value = max(max_value, secondary_diagonal_value)

    return [min_value, max_value]

 

测试一下！

grid = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

print(solution(grid))  # 输出: [3, 7]

---

回顾

• 第一个问题使用贪婪扫描从右上角开始，快速计算符合条件的值。
• 第二个问题是对角线提取，利用固定索引逻辑实现快速的O(n)解决方案。

这些都是排序结构 + 智能遍历如何导致高性能解决方案的优秀示例。

[作者]

帖子