住建网是个什么网站,四川建设网项目招标公告,邳州做网站pzwode,做店铺首页的网站编写一个高效的算法来搜索 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,17,2…
编写一个高效的算法来搜索 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
方法一
暴力求解
class Solution {public boolean searchMatrix(int[][] matrix, int target) {// 方法一 暴力求解// 遍历数组for(int i 0; i matrix.length; i){for(int j 0; j matrix[0].length; j){if(matrix[i][j] target){return true;}}}// 若遍历完数组还是没有找到目标值 返回falsereturn false;}
}
方法二
对矩阵的每一行采用二分查找进行查找
class Solution {public boolean searchMatrix(int[][] matrix, int target) {// 遍历矩阵的第一层 即每一行 使用增强for循环for(int[] row: matrix){int index binarySearch(row, target);if(index 0){return true;}}return false;}// 二分查找public int binarySearch(int[] matrix, int target){int left 0;int right matrix.length -1;while(left right){int mid (left right)/2;if(matrix[mid] target){return mid;}else if(matrix[mid] target){right mid -1;}else{left mid 1; }}// 若还未找到 返回-1return -1;}
}
方法三
Z字型查找
从矩阵的右上角0n-1进行搜索
具体过程. - 力扣LeetCode 若matrix[x,y] target,返回true若 matrix[x,y] target, 那么第y 列的所有元素都是大于target的 因此 y--若matrix[x,y] target, 那么第 x 行的所有元素都小于target 因此x
class Solution {public boolean searchMatrix(int[][] matrix, int target) {// 数组判空if(matrix.length 0){return false;}int m matrix.length; // 计算矩阵的行数int n matrix[0].length; // 计算矩阵的列数// 从右上角开始查找int x 0;int y n-1;// 循环查找while(x m y 0){if(matrix[x][y] target){return true;}else if(matrix[x][y] target){// 消去列y--;}else{// 消去行x;}}// 若循环结束 还未找到 返回falsereturn false;}
}
