题目链接

牛客网

题目描述

给定一个二维数组，其每一行从左到右递增排序，从上到下也是递增排序。给定一个数，判断这个数是否在该二维数组中。

  1. Consider the following matrix:
  2. [
  3. [1, 4, 7, 11, 15],
  4. [2, 5, 8, 12, 19],
  5. [3, 6, 9, 16, 22],
  6. [10, 13, 14, 17, 24],
  7. [18, 21, 23, 26, 30]
  8. ]
  9. Given target = 5, return true.
  10. Given target = 20, return false.

解题思路

要求时间复杂度 O(M + N)，空间复杂度 O(1)。其中 M 为行数，N 为 列数。
该二维数组中的一个数，小于它的数一定在其左边，大于它的数一定在其下边。因此，从右上角开始查找，就可以根据 target 和当前元素的大小关系来缩小查找区间，当前元素的查找区间为左下角的所有元素。
image.png

class Solution {
public:
 bool Find(int target, vector<vector<int> > array) {
     // 判断数组是否为空
     int row = array.size();
     if (row == 0) return false;
     int col = array[0].size();
     if (col == 0) return false;
     // 从右上角开始找可能的列
     for(int i = col-1;i>=0;i--){
         if(array[0][i] == target)
             return true;
         // 找到可能的列
         if(array[0][i] < target){
             for(int j=1;j<row;j++){
                 if(array[j][i] == target){
                     return true;
                 }else if(array[j][i] > target){
                     continue;
                 }
             }
         }
     }
     return false;
 }
};

或

class Solution {
public:
 bool Find(int target, vector<vector<int> > array) {
     // 判断数组是否为空
     int m = array.size();
     if (m == 0) return false;
     int n = array[0].size();
     if (n == 0) return false;
     int r = 0, c = n-1; // 右上角元素
     while (r<m && c>=0) {
         if (target == array[r][c]) {
             return true;
         }
         else if (target > array[r][c]) {
             ++r;
         }
         else {
             --c;
         }
     }
     return false;
 }
};
  • 时间复杂度：O(m+n) ，其中m为行数，n为列数，最坏情况下，需要遍历m+n次。
  • 空间复杂度：O(1)

暴力法（便历整个二维数组）：

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        if(array.size()==0||array[0].size()==0) return false;

        int c = array.size();
        int l = array[0].size();

        for(int i = 0;i < c;i++)
        {
            for(int j = 0;j < l;j++)
            {
                if(array[i][j] == target)
                {
                    return true;
                }
            }
        }
        return false;
    }
};
  • 时间复杂度：O(n^2)
  • 空间复杂度：O(1)