题目描述：在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

二维数组中的查找_牛客题霸_牛客网 (nowcoder.com)

这题的关键：每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。

既然有这个条件那得好好利用上。

可以选择传统的暴力查找的方式，但是复杂度（M行，N列）为O(M*N)。

要充分利用该数组的特殊性。

思路：我们从右上开始，如果目标值比数组元素小，说明这一列的元素都比目标值大，即这一列剩下的元素不用再考虑。与之相反，如果大于该数组元素，则说明这一行元素都比目标值小，所以也就没有必要再比较这一行的元素。这样我们就充分的利用了本体数组元素的特殊性。

实现代码：

bool Find(int target, vector<vector<int> > array) { if(array.empty()) return false; int m=0, n=array[m].size()-1; while(m < array.size() && n >= 0) //检测m，n的合法性 { if(target < array[m][n])//逻辑上删除这一列 n--; else if(target > array[m][n])//逻辑上删除这一行 m++; else return true; } return false; }

---

1.本站遵循行业规范，任何转载的稿件都会明确标注作者和来源；2.本站的原创文章，会注明原创字样,如未注明都非原创，如有侵权请联系删除！；3.作者投稿可能会经我们编辑修改或补充；4.本站不提供任何储存功能只提供收集或者投稿人的网盘链接。