来自 关于计算机 2019-11-14 16:52 的文章
当前位置: 六合联盟网 > 关于计算机 > 正文

LeetCode 74:Search a 2D Matrix

LeetCode 74:Search a 2D Matrix

Write an efficient algorithm that searches for a value in anmxnmatrix. 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]
    ]
    

    Giventarget=3, returntrue.

    Subscribeto see which companies asked this question

     class Solution {
     public:
      bool searchMatrix(vector>& matrix, int target) {
       if (matrix.size() == 0)     return false;
       if (matrix[0][0] > target)  return false;
       int r = matrix.size(), c = matrix[0].size(); //r,c分别为矩阵matrix的行数和列数
       int low = 0, high = r-1;
    
       //在所有行中利用二分查找target所在的行
      while(low <= high)
       {
        int mid = low + (high-low) / 2;
        if (matrix[mid][0] == target)
         return true;
        else if (matrix[mid][0] < target)
         low = mid + 1;
        else
         high = mid - 1;
       }
    
      //在target所在行中利用二分查找target
      int low1 = 0, high1 = c - 1;
      int k = 0;
      while (low1 <= high1)
      {
       int mid1 = low1 + (high1 - low1)/2;
       if (matrix[low-1][mid1] == target) //注意target所在的行是(low-1)
        return true;
       else if (matrix[low-1][mid1] < target)
        low1 = mid1 + 1;
       else
        high1 = mid1 - 1;
    
       k = mid1;
      }
    
      if (matrix[low-1][k] == target) 
       return true;
      else
       return false;
      }
     };
    

    图片 1

    测量试验代码:

    #include
    #include
    #include
    using namespace std;
    
     class Solution {
     public:
      bool searchMatrix(vector>& matrix, int target) {
       if (matrix.size() == 0)     return false;
       if (matrix[0][0] > target)  return false;
       int r = matrix.size(), c = matrix[0].size(); //r,c分别为矩阵matrix的行数和列数
       int low = 0, high = r-1;
    
       //在所有行中利用二分查找target所在的行
      while(low <= high)
       {
        int mid = low + (high-low) / 2;
        if (matrix[mid][0] == target)
         return true;
        else if (matrix[mid][0] < target)
         low = mid + 1;
        else
         high = mid - 1;
       }
    
      //在target所在行中利用二分查找target
      int low1 = 0, high1 = c - 1;
      int k = 0;
      while (low1 <= high1)
      {
       int mid1 = low1 + (high1 - low1)/2;
       if (matrix[low-1][mid1] == target) //注意target所在的行是(low-1)
        return true;
       else if (matrix[low-1][mid1] < target)
        low1 = mid1 + 1;
       else
        high1 = mid1 - 1;
    
       k = mid1;
      }
    
      if (matrix[low-1][k] == target) 
       return true;
      else
       return false;
      }
     };
    
    int main()
    {
     Solution s;
     vector> nums1 = { { 1, 3, 5, 7 }, { 10, 11, 16, 20 }, {23,30,34,50} };
     bool  t = s.searchMatrix(nums1, 11);
     cout << t <

74:Search a 2D Matrix Write an efficient algorithm that searches for a value in anmxnmatrix. This matrix has the following properties: Integers in each row are sorted from...

Search a 2D Matrix,search2dmatrix

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.

 

 1 class Solution {
 2 public:
 3     bool searchMatrix(vector<vector<int>>& matrix, int target) {
 4         if(matrix.size() == 0){
 5             return false;
 6         }
 7         if(matrix[0].size() == 0){
 8             return false;
 9         }
10         
11         int rowNumber = 0;
12         int colNumber = matrix[0].size()-1;
13         
14         while(rowNumber < matrix.size() && colNumber >= 0){
15             
16             if(matrix[rowNumber][colNumber] > target){
17                 colNumber--;
18             }else if(matrix[rowNumber][colNumber] < target){
19                 rowNumber++;
20             }else{
21                 return true;
22             }
23         }
24         return false;
25     }
26 };

 

a 2D Matrix,search2dmatrix 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 so...

本文由六合联盟网发布于关于计算机,转载请注明出处:LeetCode 74:Search a 2D Matrix

关键词: