目录
题目
- 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性:
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
法一、暴力
var searchMatrix = function(matrix, target) {
let m=matrix.length,n=matrix[0].length
for(let i=0;i<m;i++){
for(let j=0;j<n;j++){
if (target==matrix[i][j]){
return true
}
}
}
return false
};
- 超出时间限制,时间复杂度:O(mn)。
法二、二分查找
- 每一行都是升序,对每一行进行二分查找
var searchMatrix = function(matrix, target) {
for(const row of matrix){
const index = search(row,target)
if (index >= 0){
return true
}
}
return false
};
const search = (nums,target)=>{
let low=0,high = nums.length -1
while(low<=high){
const mid = Math.floor((high-low)/2)+low
const num = nums[mid]
if(num === target){
return mid
}else if(num>target){
high=mid-1
}else{
low=mid+1
}
}
return -1
}
- 超出时间限制,时间复杂度:O(mlogn)。对一行使用二分查找的时间复杂度为 O(logn),最多需要进行 m 次二分查找。
法三、Z 字形查找
- 每一行都是升序,对每一行进行二分查找
var searchMatrix = function(matrix, target) {
const m = matrix.length, n = matrix[0].length;
let x = 0, y = n - 1;//右上角开始
while (x < m && y >= 0) {
if (matrix[x][y] === target) {
return true;
}
if (matrix[x][y] > target) {//当前元素大于目标值,其这一列的下面元素都大于,不考虑
--y;
} else {//当前元素小于目标值,其这一行的左边元素都小于,不考虑
++x;
}
}
return false;
};
标签:二分,return,target,矩阵,II,length,查找,240,matrix
From: https://www.cnblogs.com/lushuang55/p/18535809