青海省住房和城乡建设厅官方网站吸引人的微信软文

题目描述

给定一个 m x n 的矩阵 matrix 和一个目标值 target，请你编写一个函数来判断目标值 target 是否在矩阵中。

• 每行的元素按升序排列。
• 每列的元素按升序排列。

示例 1

输入：

matrix = [[1, 4, 7, 11],[2, 5, 8, 12],[3, 6, 9, 16],[10, 13, 14, 17]
]
target = 5

输出：

true

示例 2

输入：

matrix = [[1, 4, 7, 11],[2, 5, 8, 12],[3, 6, 9, 16],[10, 13, 14, 17]
]
target = 20

输出：

false

---

解题思路

1. 暴力法

最简单的做法是遍历整个矩阵，逐个元素进行比较，看是否等于 target。这种方法的时间复杂度是 O(m * n)，其中 m 是矩阵的行数，n 是矩阵的列数。

2. 优化方法（从矩阵的角落开始）

考虑到矩阵的特点：每行和每列都是升序排列的，我们可以利用这一点来提高搜索效率。

一种常见的优化方法是从矩阵的右上角或者左下角开始搜索。这里我们选择从右上角开始：

• 如果目标值等于当前位置的值，直接返回 true。
• 如果目标值小于当前位置的值，则可以排除当前列，因为该列的元素都大于当前位置的值，移动到当前行的左边（即向左移动）。
• 如果目标值大于当前位置的值，则可以排除当前行，因为该行的元素都小于当前位置的值，移动到当前列的下方（即向下移动）。

这种方法的时间复杂度是 O(m + n)，比暴力法更高效。

实现代码（右上角开始）

#include <stdio.h>
#include <stdbool.h>bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target) {int m = matrixSize; // 矩阵的行数int n = *matrixColSize; // 矩阵的列数int row = 0;int col = n - 1; // 从右上角开始while (row < m && col >= 0) {if (matrix[row][col] == target) {return true; // 找到目标值} else if (matrix[row][col] < target) {row++; // 目标大于当前值，向下移动} else {col--; // 目标小于当前值，向左移动}}return false; // 未找到目标值
}int main() {// 示例矩阵int matrix[4][4] = {{1, 4, 7, 11},{2, 5, 8, 12},{3, 6, 9, 16},{10, 13, 14, 17}};int matrixSize = 4;int matrixColSize = 4;int target = 5;// 使用动态数组传递矩阵int* matrixPtr[4];for (int i = 0; i < matrixSize; i++) {matrixPtr[i] = matrix[i];}bool result = searchMatrix(matrixPtr, matrixSize, &matrixColSize, target);if (result) {printf("Found %d in the matrix.\n", target);} else {printf("%d not found in the matrix.\n", target);}return 0;
}

解释

1. 矩阵初始化：

   • 在 main 函数中，我们定义了一个 4x4 的静态二维数组 matrix，并将其转换为指针数组 matrixPtr，用于传递给 searchMatrix 函数。

2. 搜索方法：

   • searchMatrix 函数从矩阵的右上角开始搜索，通过比较当前值与目标值的大小来决定向下或向左移动。
   • 如果目标值等于当前元素，返回 true；如果目标值小于当前元素，向左移动；如果目标值大于当前元素，向下移动。

3. 返回值：

   • 如果在搜索过程中找到了目标值，返回 true；否则返回 false。

时间复杂度和空间复杂度

• 时间复杂度：

  • 每次操作后，我们要么向下移动一行，要么向左移动一列。所以，最多需要 m + n 次操作，其中 m 是矩阵的行数，n 是矩阵的列数。因此时间复杂度是 O(m + n)。

• 空间复杂度：

  • 只使用了常数额外空间，所以空间复杂度是 O(1)。