JS Leetcode 74. 搜索二维矩阵题解分析，二分法与坐标轴法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了JS Leetcode 74. 搜索二维矩阵题解分析，二分法与坐标轴法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3233字，纯文字阅读大概需要5分钟。
内容图文
壹 ? 引
本题来自Leetcode74. 搜索二维矩阵，虽然难度是中等，但如果站在做出来的角度，你会发现其实并不难，题目描述如下：
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。示例 1：
输入：
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
示例 2：输入：
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104
贰 ? 简单的题解分析
我们简单提取下题目信息，给定一个二维数组，每个子数组都满足升序排列，且每后一排子数组的第一个元素，一定大于上一排子数组的最后一个元素。而题目要求就是给定一个目标值，让我们在这个二维数组中查询，如果存在返回true，不存在则返回false。
贰 ? 壹 暴力解法
我们可以直接遍历数组中的每个子数组，相当于完整遍历一次所有数字，从头到尾看是否有与目标值相同的值即可，思路清晰且简单，这里就不贴实现代码了。
贰 ? 贰 二分法
我在JS leetcode 寻找旋转排序数组中的最小值 题解分析，你不得不了解的二分法一题中，曾简单科普过二分法，相对于暴力做法时间复杂度O(n)，二分法因为每次查找都只需要考虑一般的元素，所以时间复杂度为O(logn)，所以我当时看到此题，第一想法是给数组降维，然后直接套用二分法的模板，直接上代码：
/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var searchMatrix = function (matrix, target) {
// 打平为一维数组
let arr = matrix.flat(2);
// 使用二分法进行查找
// 定义左边界
let l = 0;
// 定义右边界
let r = arr.length - 1;
while (l <= r) {
// 取中间数
mid = Math.floor((l + r) / 2);
// 如果相等直接返回
if (arr[mid] === target) {
return true;
} else if (arr[mid] < target) {
l = mid + 1;
} else if (arr[mid] > target) {
r = mid - 1;
};
};
return false;
};
因为数组的子数组都满足升序，且后面的元素必定大于前面的数组，即便我们降维后依旧满足整体数组为升序数组的条件，因此可以使用二分法。
我们每次都找中间数，判断是否与目标数相等，相等直接返回。但如果不相等，就需要区分与目标数的大小差异了，如果中间数比目标值要小，那说明目标数必不可能在中间数的左边区间，因此需要修改左边界后，开始继续查找右边区间，反之亦然。
贰 ? 叁 坐标轴法
我在逛题解时，看到了一个让我眼前一亮的做法，那就坐标轴法，题解灵感来自于【坐标轴法】搜索二维矩阵
这个思路其实非常好理解，我们来看个坐标图，以题目中二维数组为例：
每行数组都满足升序，第一个最小，越往右边越大。
每列数组从下往上满足降序，越往上越小，且每行数组最后一个数都比下一列第一个数小。
我们用图将例子中查找3的过程画出来就是这样：
思路很简单，倒序查找二维数组，因为最后一行第一个数都比3大，而且我们已知每行数组是升序，那说明这一行后面的数字都不用看了，直接看上一行。
第二次从倒数第二行开始查找，结果10还是比3大，这一行后面的数组也不用看了，继续往上。
第三次我们遇到了1，这次1比3要小，因为每行数组是升序，我们继续看看1后面的数字有没有跟3相等的，结果很幸运，我们找到了目标值，返回true即可。
我们用代码表示这个过程：
/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var searchMatrix = function (matrix, target) {
// 分别定义x轴与y轴计数
let y = matrix.length - 1, x = 0;
while (y >= 0 && x < matrix[0].length) {
if (matrix[y][x] === target) {
return true;
// 如果某排数组第一个元素都比目标值大，y轴上移
} else if (matrix[y][x] > target) {
y--;
} else {
// 反之x轴右移
x++;
}
};
return false;
};
注释和图解都很详细了，那么本题就记录到这里了。
内容总结
以上是互联网集市为您收集整理的JS Leetcode 74. 搜索二维矩阵题解分析，二分法与坐标轴法全部内容，希望文章能够帮你解决JS Leetcode 74. 搜索二维矩阵题解分析，二分法与坐标轴法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。