leetcode—搜索二维矩阵II

编写一个高效的算法来搜索 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字型查找

从矩阵的右上角（0，n-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;}
}