首页 > 代码库 > [LeetCode] Search a 2D Matrix

[LeetCode] Search a 2D Matrix

2024-07-09 22:45:01   219人阅读

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处于的行，即在所有行的第一元素中找第一个比target小的元素。

// 注意，此处mid= （low+high+1）/2, 不是 mid = （low+high）/2
// 原因是此处要找的是第一个比target小的数，当array[mid] < target 时，low =mid，
// low仍然在我们的搜索范围之中，我们让high逐渐比较low。
// 举例，array={2,5}， low=0，high=1，target=3，
// 如果mid = （low+high）/2就会进入死循环，我们要让mid更接近high
// 如果要找的是第一个比target大的数，则使用mid = （low+high）/2，可以参考我自己写的upper_bound函数

 1 class Solution 2 { 3     public: 4         bool searchMatrix(vector<vector<int> > &matrix, int target) 5         { 6             int rowNum =  matrix.size(); 7             int colNum =  matrix[0].size(); 8  9             int rowLow = 0;10             int rowHigh = rowNum - 1;11 12         // step1. 找到合适的行，找到比某行的第一个元素比target小的那一行13             while(rowLow < rowHigh)14             {15         // 注意，此处mid= （low+high+1）/2, 不是 mid = （low+high）/216         // 原因是此处要找的是第一个比target小的数，当array[mid] < target 时，low =mid，17         // low仍然在我们的搜索范围之中，我们让high逐渐比较low。18         // 举例，array={2,5}， low=0，high=1，target=3，19         // 如果mid = （low+high）/2就会进入死循环，我们要让mid更接近high20         // 如果要找的是第一个比target大的数，则使用mid = （low+high）/2，可以我的参考upper_bound函数21                 int mid = (rowLow + rowHigh + 1)/2;22                 if(matrix[mid][0] ==  target)23                     return true;24                 if(matrix[mid][0] < target)25                     rowLow = mid ;26                 else27                     rowHigh = mid - 1 ;28 29             }30 31         //step2. 在行内二分32             int colLow = 0;33             int colHigh = colNum - 1;34             while(colLow <= colHigh)35             {36                 int mid = (colLow + colHigh)/2;37                 if(matrix[rowLow][mid] == target)38                     return true;39                 if(target > matrix[rowLow][mid] )40                     colLow = mid + 1;41                 else42                     colHigh = mid - 1;43 44             }45             return false;46 47 48         }49 };

 方法二：将matrxi当成一个有序的大数组，直接二分法，只是计算出的mid要换算成行和列

 1 class Solution 2 { 3     public: 4         bool searchMatrix(vector<vector<int> > &matrix, int target)  5         {    6      7             int rowNum =  matrix.size(); 8             int colNum =  matrix[0].size(); 9     10             int low = 0;11             int high = rowNum * colNum - 1;12             int mid = 0;13             int row = 0, col = 0;14 15             while(low <= high)16             {   17                 mid = (low + high) /2; 18     19                 row = mid/colNum;20                 col = mid%colNum;21 22                 if(matrix[row][col] == target)23                     return true;24                 if(matrix[row][col] > target)25                     high = mid -1; 26                 else27                     low = mid +1; 28             }   29             return false;30 31         } 32 };

 


联系
我们