leetcode hot 100 搜刮二维矩阵II

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

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

示例 1：

1. <strong>输入：</strong>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
2. <strong>输出：</strong>true

复制代码

示例 2：

1. <strong>输入：</strong>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
2. <strong>输出：</strong>false

复制代码

提示：

• m == matrix.length
  
• n == matrix.length
  
• 1 <= n, m <= 300
  
• -109 <= matrix[j] <= 109
  
• 每行的全部元素从左到右升序排列
  
• 每列的全部元素从上到下升序排列
  
• -109 <= target <= 109
  

1. class Solution {
2.     public boolean searchMatrix(int[][] matrix, int target) {
3.         //这道题是二维矩阵 ，有特殊的性质
4.         // 每行的元素从左到右升序排列。
5.         // 每列的元素从上到下升序排列
6.         // 首先，可以O（n^2） for循环遍历查询 但是没有利用这个矩阵的性质
7.         // 首先看矩阵的四个点
8.         // 左上角 向右变大 向下变大 不可用
9.         // 左下角 向上变小 向右变大 可用
10.         //右上角 向下变大 向左变小 可用
11.         //右下角不可用
12.         // 左下角 ，右上角可以使用
13.         // 左下角
14.         int x=matrix.length-1;
15.         int y=0;
16.         while(x>=0 && y<matrix[0].length){
17.             if(matrix[x][y]==target) return true;
18.             else{
19.                 //目标值比该值小往上移
20.                 if(matrix[x][y]>target) x--;
21.                 //目标值比该值大往右移
22.                 else          y++;
23.             }
24.         }
25.         return false;
26.     }
28. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。