在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
从左下角出发,如果要找的数小于当前数,那么当前数的下、右以及右下的数都大于要找的数,则向上走一步;如果要找的数大于当前数,类似理由,则向右走一步;找的了则中途返回true,否则最后返回false。算法正确性证明可以由数学归纳法得到,只需证明如果矩阵里含a aa,上述算法一定会中途走到a aa这个数。显然当矩阵的行或列是1 11的时候算法正确,考虑m × n m\times nm×n矩阵的情况,由于第一步走完之后一定能保证要找的数在( m − 1 ) × n (m-1)\times n(m−1)×n或者m × ( n − 1 ) m\times (n-1)m×(n−1)这两种类型的矩阵之一中存在,由归纳假设,算法接下来能找到要找的数,由数学归纳法,算法正确。代码如下:
#include <vector>
using namespace std;
class Solution {
public:
bool searchArray(vector<vector<int>> array, int target) {
int x = array.size() - 1, y = 0;
while (x >= 0 && y < array[0].size()) {
if (array[x][y] < target) y++;
else if (array[x][y] > target) x--;
else return true;
}
return false;
}
};
你这
韩版
???