搜索二维矩阵 II(java)

题目描述

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

代码思路：

用暴力算法：

class Solution {public boolean searchMatrix(int[][] matrix, int target) {// boolean flag = false;if(matrix==null ||matrix.length==0 ||target<matrix[0][0]){return false;}int n=matrix.length;int m=matrix[0].length;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(matrix[i][j]==target){return true;}else if(matrix[i][j]>target){break;}}}return false;}
}

巧妙的方法：

这个把他看做一个二叉搜索树，其中右上角点是根节点，往下是右子树，往左是左子树。复杂度O（log(M*N)）

class Solution {public boolean searchMatrix(int[][] matrix, int target) {if(matrix==null ||matrix.length==0 ||target<matrix[0][0]){return false;}int n=matrix.length;int m=matrix[0].length;int i = 0;int j = m-1;while(true){if(matrix[i][j]==target){return true;}else if(matrix[i][j]>target){j--;if(j<0){return false; }}else{i++;if(i>n-1){return false;}}}}
}