文章目录
- 搜索二维矩阵
- 我的思路
- 网上思路
- 总结
搜索二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵:
● 每行中的整数从左到右按非严格递增顺序排列。
● 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,返回 false 。
示例 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
我的思路
循环,尝试二分法
网上思路
二分法
我的思路
var searchMatrix = function (matrix, target) {if (matrix.length === 0 || matrix[0].length === 0) {return false;}const rows = matrix.length;const cols = matrix[0].length;for (let i = 0; i < rows; i++) {if (target < matrix[i][0]) {return false;}if (target > matrix[i][cols - 1]) {continue;}for (let j = 0; j < cols; j++) {if (matrix[i][j] === target) {return true;}}}return false;
};
讲解
双重循环,主要是以下边界条件进行判断
- 如果 target 小于当前行的第一个元素,直接返回 false。
- 如果 target 大于当前行的最后一个元素,继续检查下一行。
网上思路
var searchMatrix = function(matrix, target) {const m = matrix.length, n = matrix[0].length;let low = 0, high = m * n - 1;while (low <= high) {const mid = Math.floor((high - low) / 2) + low;const x = matrix[Math.floor(mid / n)][mid % n];if (x < target) {low = mid + 1;} else if (x > target) {high = mid - 1;} else {return true;}}return false;
};
讲解
若将矩阵每一行拼接在上一行的末尾,则会得到一个升序数组,我们可以在该数组上二分找到目标元素。
代码实现时,可以二分升序数组的下标,将其映射到原矩阵的行和列上。
- 初始化两个指针 low 和 high。low 指向矩阵的 起始位置(0),high 指向矩阵的 结束位置(总元素数 - 1)。
- 当 low 小于或等于 high 时,继续进行查找。
- 计算中间位置 mid。这里使用了 (high - low) / 2 来避免直接相加可能导致的溢出。
- 将一维索引 mid 转换为二维索引:
- 行索引为 Math.floor(mid / n),表示当前元素在矩阵中的行。
- 列索引为 mid % n,表示当前元素在矩阵中的列。
- 这样就可以通过 x 获取当前中间位置的元素。
- 如果当前元素 x 小于 target,则目标值一定在右半部分,因此将 low 更新为 mid + 1。
- 如果当前元素 x 等于 target,则找到了目标值,返回 true。
总结
很实用,正好我自身有项目在使用二维矩阵,明天我来试试