首页 > 代码库 > 【leetcode刷题笔记】Search a 2D Matrix

【leetcode刷题笔记】Search a 2D Matrix

2024-07-12 13:41:03   220人阅读

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

 

  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

 

For example,

Consider the following matrix:

[  [1,   3,  5,  7],  [10, 11, 16, 20],  [23, 30, 34, 50]]

Given target = 3, return true.

 

题解：每次用右上角的元素跟target比较，有三种情况：

  1. 相等，说明找到了target；
  2. 右上角元素比target元素大，那么说明target在第一行，递归的搜索第一行。
  3. 右上角元素比target元素小，那么说明target在第二行及以后，递归的搜索如下图所示区域：

代码如下：

 1 public class Solution { 2     private boolean IfFind = false; 3     private void RightCornerRecur(int[][] matrix,int target,int m_start,int m_end,int n_start,int n_end){ 4         if(m_start > m_end || n_start > n_end) 5             return; 6              7         if(m_start < 0 || n_start < 0 || m_end >= matrix.length || n_end >= matrix[0].length) 8             return; 9         10         if(matrix[m_start][n_end] == target){11             IfFind = true;12             return;13         }14         if(matrix[m_start][n_end] > target)15             RightCornerRecur(matrix, target, m_start, m_start, n_start, n_end-1);16         else {17             RightCornerRecur(matrix, target, m_start+1,m_end, n_start, n_end);18         }19 20     }21     public boolean searchMatrix(int[][] matrix, int target) {22         RightCornerRecur(matrix, target,0,matrix.length-1, 0, matrix[0].length-1);23         return IfFind;24     }25 }

右上角可以用来比较剪掉一些元素，左下角同样可以，下面的代码中加上了左下角元素与target元素的比较，最终的运行时间是384ms，而上述只考虑右上角的运行时间是472ms。

 1 public class Solution { 2     private boolean IfFind = false; 3     private void RightCornerRecur(int[][] matrix,int target,int m_start,int m_end,int n_start,int n_end){ 4          5         if(m_start > m_end || n_start > n_end) 6             return; 7              8         if(m_start < 0 || n_start < 0 || m_end >= matrix.length || n_end >= matrix[0].length) 9             return;10         11     12         if(matrix[m_start][n_end] == target){13             IfFind = true;14             return;15         }16         17         if(matrix[m_start][n_end] > target)18             RightCornerRecur(matrix, target, m_start, m_start, n_start, n_end-1);19         20         else {21             if(matrix[m_end][0] == target){22                 IfFind = true;23                 return;24             }25             if(matrix[m_end][0] < target)26                 RightCornerRecur(matrix, target, m_end, m_end, n_start+1, n_end);27             else28                 RightCornerRecur(matrix, target, m_start+1,m_end-1, n_start, n_end);29         }30 31     }32     public boolean searchMatrix(int[][] matrix, int target) {33         RightCornerRecur(matrix, target,0,matrix.length-1, 0, matrix[0].length-1);34         return IfFind;35     }36 }


联系
我们