建设银行申请信用卡网站首页,做短视频的网站都有哪些,宁德网站建设,双人网页游戏网站文章目录 搜索二维矩阵我的思路网上思路 总结 搜索二维矩阵 给你一个满足下述两条属性的 m x n 整数矩阵#xff1a; ● 每行中的整数从左到右按非严格递增顺序排列。 ● 每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target #xff0c;如果 target 在矩阵中 ● 每行中的整数从左到右按非严格递增顺序排列。 ● 每行的第一个整数大于前一行的最后一个整数。 给你一个整数 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 指向矩阵的 起始位置0high 指向矩阵的 结束位置总元素数 - 1。当 low 小于或等于 high 时继续进行查找。计算中间位置 mid。这里使用了 (high - low) / 2 来避免直接相加可能导致的溢出。将一维索引 mid 转换为二维索引 行索引为 Math.floor(mid / n)表示当前元素在矩阵中的行。列索引为 mid % n表示当前元素在矩阵中的列。这样就可以通过 x 获取当前中间位置的元素。 如果当前元素 x 小于 target则目标值一定在右半部分因此将 low 更新为 mid 1。如果当前元素 x 等于 target则找到了目标值返回 true。 总结
很实用正好我自身有项目在使用二维矩阵明天我来试试
