wordpress代码增强插件下载,网站建设加优化,网站开发价格多少,做两个网站 之间超链接240.编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性#xff1a; 每行的元素从左到右升序排列。 每列的元素从上到下升序排列。 示例 1#xff1a; 输入#xff1a;matrix [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,… 240.编写一个高效的算法来搜索 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 示例 2 输入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 两个示例为同一矩阵 仔细观察你会发现如果以右上角为顶点逆时针旋转 45o这就类似于二叉搜索树左边的数都小于父节点右边的数都大于右节点所以我们从顶点 matrix[i,j] 开始搜索当它小于 target 我们就 i1 去往右节点当它大于 target 我们就 j-1 去左顶点 public boolean searchMatrix(int[][] matrix, int target) {int row 0, col matrix[0].length - 1;while(row matrix.length col 0){if(matrix[row][col] target)col--;else if(matrix[row][col] target)row;else return true;}return false;}说实话想到有序应该最先想到二分我们直接遍历每一行进行二分查找由于矩阵从上到下也是升序所以在从上到下遍历每一行时左上角也就是当前遍历行的行首为未查找部分矩阵的最小值target 小于行首则说明小于剩下的所有值那直接可以退出循环返回 false 了而如果 target 大于行尾则直接查下一行即可。 public boolean searchMatrix(int[][] matrix, int target) {int n matrix[0].length - 1;for(int i0;imatrix.length;i){if(matrix[i][0] target)break;if(matrix[i][n] target)continue;int col binarySearch(matrix[i], target);if (col ! -1) return true;}return false;}public int binarySearch(int[] nums, int target){int left 0, right nums.length - 1;int mid -1;while(left right){mid left (right - left) / 2;if(nums[mid] target)return mid;if(nums[mid] target) left mid 1;else right mid - 1;}return -1;}
