0074._Search_a_2D_Matrix.md

074. Search a 2D Matrix

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/search-a-2d-matrix/

内容描述

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
Example 1:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
Output: true
Example 2:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
Output: false

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******

• 可以将这个二维数组看做一个数组，以二分法查找为最优算法

代码：

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
    if(matrix.length===0)
        return false;
    var row=0,col=matrix[0].length-1;
    while(row<matrix.length&&col>=0){
        if(matrix[row][col]===target)
            return true;
        else if(matrix[row][col]>target)
            col--;
        else
            row++;
    }
    return false;
};