矩阵可以隐藏出令人惊讶的优雅模式——尤其是当它们与递归思维和高效算法结合时。在这篇文章中，我们将探讨两个有趣的矩阵问题，这些问题将考验你的逻辑思维，并帮助你掌握矩阵遍历技术！
问题一：计算小于目标值的元素个数
问题
给定一个矩阵，其中：
- 每一行都是升序排列
- 每一列也都是升序排列
你的任务是？编写一个函数，计算有多少元素小于给定的目标值。没错——你需要在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)解决方案。
这些都是排序结构 + 智能遍历如何导致高性能解决方案的优秀示例。
