0074._Search_a_2D_Matrix

发表于 分类于 ， ，

074. Search a 2D Matrix

难度: Medium

刷题内容

原题连接

内容描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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)**

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

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @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;
};