跳转至

74. 搜索二维矩阵

难度：中等

题目

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

  • 每行中的整数从左到右按升序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

示例 1：

Example 1

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

Example 1

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -10^4 <= matrix[i][j], target <= 10^4

Reference

题解

根据矩阵的特性可知，假设矩阵为\(\{a_{ij}\}_{m\times n}\)，目标值\(t\)位于坐标\((i^*, j^*)\)处，有：

  • 对于任何\(i, j\)，若\(i < i^*\)，则\(a_{ij} < t\)，当\(i = i^*\)时，若\(j < j^*\)，则\(a_{ij} < t\)
  • 对于任何\(i, j\)，若\(i > i^*\)，则\(a_{ij} > t\)，当\(i = i^*\)时，若\(j > j^*\)，则\(a_{ij} < t\)

即目标值将矩阵分为两部分：右侧和下侧的所有元素大于等于目标值，左侧和上侧的所有元素小于等于目标值。

从矩形的左下角开始：

  • 若当前位置的数值小于目标值，说明目标值位于当前行，因此向右移动即可找到目标值
  • 若当前位置的数值大于目标值，说明目标值不在当前行，需要向上移动

重复如上过程，直至找到目标元素。

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target){
    int x = matrixSize - 1, y = 0;
    while (x >= 0 && y < *matrixColSize)
    {
        if (matrix[x][y] < target)
            y++;
        else if (matrix[x][y] > target)
            x--;
        else
            return true;
    }
    return false;
}

以上算法可以使用二分查找进行优化。

评论