海南营销网站建设,被代运营骗了去哪投诉,宁波住房建设局网站,沙洋建设局网站74. 搜索二维矩阵#xff08;中等#xff09; 方法一#xff1a;二分查找
思路 总体思路 由于二维矩阵固定列的「从上到下」或者固定行的「从左到右」都是升序的 因此我们可以使用两次二分来定位到目标位置。 第一次二分#xff1a; 从第 0 列中的「所有行」开始找#x…74. 搜索二维矩阵中等 方法一二分查找
思路 总体思路 由于二维矩阵固定列的「从上到下」或者固定行的「从左到右」都是升序的 因此我们可以使用两次二分来定位到目标位置。 第一次二分 从第 0 列中的「所有行」开始找找到合适的行 row 即找到最后一个满足 matrix[x][0] target 的行号第二次二分从 row 中「所有列」开始找找到合适的列 col 即找到最后一个满足 matrix[row][y] target 的列号。 二分代码解释 这里用到了二分查找的高级模板left mid用于查找数组中当前索引及其直接左邻居索引的元素或条件。 注意while 语句的条件是 left right 。 此外mid 值计算需要 1 如果不加 1 会出现死循环比如l 2, r 3 的时候如果不加 1在满足 l mid 的情况下会一直死循环。 int binarySearch(vectorint nums, int target){if(nums.size() 0)return -1;int left 0, right nums.size();while(left right){// Prevent (left right) overflowint mid left (right - left) / 2;if(nums[mid] target){ return mid; }else if(nums[mid] target) { left mid; }else { right mid 1; }}// Post-processing:// End Condition: left rightif(left ! nums.size() nums[right] target) return right;return -1;}代码
class Solution {
public:bool searchMatrix(vectorvectorint matrix, int target) {int m matrix.size(), n matrix[0].size();int row, col;int left 0, right m-1;// 第一次二分找到最后一个不大于目标值的元素的所在行while(left right){int mid left (right - left 1) / 2;if(matrix[mid][0] target) left mid;else right mid - 1;}row right;// 可以先判断减少时间复杂度if(matrix[row][0] target) return true;if(matrix[row][0] target) return false;// 第二次二分找到所在列left 0, right n-1;while(leftright){int mid left (right - left 1) / 2;if(matrix[row][mid] target) left mid;else right mid - 1;}col right;return matrix[row][col] target;}
};方法二一次二分
思路
如果将数组按行逐元素连接起来那么数组将形成一个单调递增序列我们可以使用一次二分在该 “一维数组” 中查找如果找到target 返回 true否则返回false。对于一次二分因为只有找到 target 和 没找到 target 两种情况所以只需要普通的模板。
代码
class Solution {
public:bool searchMatrix(vectorvectorint matrix, int target) {int m matrix.size(), n matrix[0].size();int left 0, right m * n - 1;// 一次二分while(left right){int mid left (right - left) / 2;if(matrix[mid/n][mid%n] target) return true;else if(matrix[mid/n][mid%n] target) left mid 1;else right mid - 1; }return false;}
};方法三抽象二叉搜索树
思路 我们可以将二维矩阵抽象成「以右上角为根的 BST」 那么我们可以从根右上角开始搜索如果当前的节点不等于目标值可以按照树的搜索顺序进行 当前节点「大于」目标值搜索当前节点的「左子树」也就是当前矩阵位置的「左方格子」即 y–当前节点「小于」目标值搜索当前节点的「右子树」也就是当前矩阵位置的「下方格子」即 x。
代码
class Solution {
public:bool searchMatrix(vectorvectorint matrix, int target) {int m matrix.size(), n matrix[0].size();// 当前的坐标值从右上角开始查找int x 0, y n-1;while(check(x, y, m, n) matrix[x][y] ! target){// 如果matrix[x][y] target 说明需要向左查找if(matrix[x][y] target) y--;// 如果matrix[x][y] target 说明需要向下查找else if(matrix[x][y] target) x;}return check(x, y, m, n) matrix[x][y] target;}// 边界情况判断bool check(int x, int y, int m, int n){return x0 xm y0 yn;}
};参考资料 二分查找的三种模板C版 【宫水三叶】一题双解「二分」「抽象 BST」解法
