4
日拱算法：搜索二维矩阵 II_安东尼漫长的技术岁月的技术博客_51CTO博客
source link: https://blog.51cto.com/u_13961087/5434528
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
日拱算法：搜索二维矩阵 II
原创- 题目来源： LeetBook /算法面试题汇总
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。 每列的元素从上到下升序排列。
示例 1：
输入：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
输出：true
输入：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
输出：false
此题要利用到【每行的元素从左到右升序排列。 每列的元素从上到下升序排列】这个关键的题干信息。
咱就是说，只要是查找目标值，有了排序，都会方便许多。
思路：从矩阵的右上角（或左下角）的值开始比较；
比如：从矩阵右上角的值开始找，那就是第一行的最后一个数字；
- 如果目标值刚好等于右上角的值，则返回输出；
- 如果目标值小于右上角值，则目标值肯定是在同一行的左边去找；
- 如果目标值大于右上角的值，则到下一行去找；
var searchMatrix = function(matrix, target) {
let col = matrix[0].length - 1;//列
let row = 0;//行
while (col >= 0 && row <= matrix.length - 1) {
if (target == matrix[row][col]) {
//如果找到就直接返回
return true;
} else if (target < matrix[row][col]) {
//目标值小于右上角值，下一步往左找
col--;
} else if (target > matrix[row][col]) {
//目标值大于右上角值，下一步往下找
row++;
}
}
return false;
};
let col = matrix[0].length - 1;//列
let row = 0;//行
while (col >= 0 && row <= matrix.length - 1) {
if (target == matrix[row][col]) {
//如果找到就直接返回
return true;
} else if (target < matrix[row][col]) {
//目标值小于右上角值，下一步往左找
col--;
} else if (target > matrix[row][col]) {
//目标值大于右上角值，下一步往下找
row++;
}
}
return false;
};
那么，相应的，从左下角，找的思路就是反过来的，不做赘述：
var searchMatrix = function(matrix, target) {
let col = 0, row = matrix.length - 1;
while(row >= 0 && col < matrix[0].length){
if(target > matrix[row][col]){
col++;
}else if(target < matrix[row][col]){
row--;
}else{
return true;
}
}
return false;
};
let col = 0, row = matrix.length - 1;
while(row >= 0 && col < matrix[0].length){
if(target > matrix[row][col]){
col++;
}else if(target < matrix[row][col]){
row--;
}else{
return true;
}
}
return false;
};
OK，以上便是本篇分享。点赞关注评论，为好文助力👍
我是掘金安东尼 🤠 100 万阅读量人气前端技术博主 💥 INFP 写作人格坚持 1000 日更文 ✍ 关注我，陪你一起度过漫长编程岁月 🌏
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK