二维数组中的查找

ryluo 2020-06-19 21:37:00

在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。

请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

样例

输入数组:

[
  [1,2,8,9],
  [2,4,9,12],
  [4,7,10,13],
  [6,8,11,15]
]

如果输入查找数值为7,则返回true,

如果输入查找数值为5,则返回false。

分析:

这道题可以从右上角或者左下角开始遍历该数组,加入从右上角开始遍历。

如果target小于右上角的值,那么右上角对应的那一列就可以删除

如果target大于右上角的值,那么右上角对应的哪一行就可以删除

时间复杂度为O(m+n)

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

        int i = 0, j = array[0].size() - 1;
        while(i < array.size() && j >= 0){
            if (array[i][j] == target) return true;

            if (target < array[i][j]) j--;  
            else i++;                       
        }

        return false;
    }
};

// 左下角
// class Solution {
// public:
//     bool searchArray(vector<vector<int>> array, int target) {
//         if(array.empty() || array[0].empty()) return false;

//         int i = array.size() - 1, j = 0;
//         while(i >= 0 && j < array[0].size()){
//             if (array[i][j] == target) return true;

//             if (target > array[i][j]) j++;  
//             else i--;                       
//         }

//         return false;
//     }
// };