408算法练习——搜索二维矩阵

2021/8/6 1:38:56

本文主要是介绍408算法练习——搜索二维矩阵,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

搜索二维矩阵

问题链接:https://leetcode-cn.com/problems/search-a-2d-matrix-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


示例 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
 

提示:

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

 

二、问题分析

  根据题目给出的二维数组特点可以看出这个数组是有序的,如果类比一维有序数组中的查找,可以想到二分法。但是怎么对二维数组进行二分就很不容易想,先分析一下数据结构,对于整个矩阵中的子矩阵,可以看出子矩阵最右下角元素的值的整个矩阵的最大值,相应的,左上角的值是该子矩阵的最小值,这个性质很容易验证,只需要结合题目给出的矩阵的规则就不难验证。

  既然已经知到一个矩阵中最小值在左上角,最大值在右上角,就应该运用这个性质,我们可以不断的压缩整个数组,当遍历到某个值时,如果该值大于目标值,那么我们可以保证该元素的下方和右方,不包含目标元素,同样的如果当前值比目标值小,所以以该节点为界,节点左上方的空间不包含目标元素。

  根据上文推断出的两个性质,我们可以对数组中的节点进行判断,而且每次判断都对数组进行逻辑上的压缩(即不需要再遍历某些节点)。

  出发点的选择,我们需要排除的元素是当前元素的左上方或右下方,如果从整个矩阵的左上方出发,当下移指针的时候就新添加了某些节点,但是就不能判断这些节点中有没有要找的元素,如果从左下方和右上方出发,因为该处节点必定时一列(一行)中的最大值,那么就可以确定该行或该列中有没有目标元素。

  通俗来讲,如果从左上角或右下角出发实际上不是在压缩数组,而是在不断往数组中添加新元素,而从左下角或右上角,因为该处节点已经是一列或者一行中的最大值,同时又是一行或一列的最小值,就很容易对目标值进行判断(实际压缩了数组)

  

 

 

 

 三、算法实现

  代码:

 1 class Solution {
 2     public boolean searchMatrix(int[][] matrix, int target) {
 3         int m = matrix.length;//m为行数
 4         int n = matrix[0].length;//n为列数
 5         int i = m-1;//i定义为指针行下标,j为指针列下标,从左下角开始遍历
 6         int j = 0;
 7         while(i>=0 && j<n){
 8             if(matrix[i][j] == target){
 9                 return true;
10             }else if(matrix[i][j] > target){
11                 i--;
12             }else if(matrix[i][j] < target){
13                 j++;
14             }
15         }
16         return false;
17     }
18 }

 



这篇关于408算法练习——搜索二维矩阵的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程