力扣第 74 题是 搜索二维矩阵

题目描述

给定一个 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)。