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;
};
