Leetcode240. 搜索二维矩阵 II

题目描述

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

示例 1：

img

1
2
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

示例 2：

img

1
2
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= n, m <= 300
  • −109<=matix[i][j]<=109-10^9 <= matix[i][j] <= 10^9
  • 每行的所有元素从左到右升序排列
  • 每列的所有元素从上到下升序排列
  • −109<=target<=109-10^9 <= target <= 10^9

解题思路

在编写高效算法的过程中我们要尽可能地利用这个矩阵的两个特性：

每行的元素从左到右升序排列

每列的元素从上到下升序排列

那么这个矩阵右上角的元素就是这个矩阵的中位数，利用这两个特性我们可以写出类似于二分查找的代码。

从右上角元素开始，如果target比当前元素小，就去查找这个元素同一行的左边元素，否则就去查找这个元素同一列的下一个元素。

据此可以写出相关代码，具体细节见示例代码。

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool searchMatrix(vector<vector<int>>& matrix, int target)
{
    int row=0;
    int col=matrix[0].size()-1;
    while(row<matrix.size()&&col>=0)
    {
        if(target==matrix[row][col]) 
        {
            return true;
        }
        else if(target<matrix[row][col])
        {
            col--;
        }
        else
        {
            row++;
        }
    }
    return false;
}

时间复杂度为：O(m+n)O(m+n)，mm和nn分别为矩阵的行数和列数

空间复杂度为：O(1)O(1)