《剑指offer》二维数组中的查找

题目链接：?rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

思路

按照书中的思路，首先选数组中右上角的数字，如果该数字等于要查找的数字，由于这个数字行递增与列递增的特性，那么就要剔除整列，如果该数字小于要查找的数字，，那么就剔除一整行。

根据这个数组的特殊性，我们每次一整行一整列的剔除，最后就能得到我们想要的结果。

class Solution{public:bool Find(vector<vector<int> > array,int target){int n = array.size();if(n==0) return 0;int m = array[0].size();int r = 0,c = m-1;while(true){if(r>=n || c<0)return false;if(array[r][c]>target)c–;else if(array[r][c]<target)r++;elsereturn true;}}};

即使爬到最高的山上，一次也只能脚踏实地地迈一步。

相关文章：

你感兴趣的文章：

标签云：