剑指offer算法题（一）二维数组中的查找

布满荆棘的人生 2022-05-14 14:38 76阅读 0赞

剑指offer算法题（一）  
题目1：二维数组中的查找  
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

思路分析：   
从左上往右下方来解决这个问题   
例如在如下的矩阵中查找数字27：

6    7    9    10  
10    13    19    23  
20    27    29    31  
26    28    39    40  
定义矩阵的行数为 row, 列数为 col;   
设置 i = 0, j = col-1;   
从10开始，当数字小于27时，代表这一行均小于27，这一行其它数字不用再去比较：i++;

10    13    19    23  
20    27    29    31  
26    28    39    40  
此时比较对象变为23，当数字小于27时，代表这一列该数字以下的数字均大于27，无需比较：j–;

10    13    19  
20    27    29  
26    28    39  
比较对象变为19，大于27，i++;   
比较对象变为29，小于27，j–;   
比较对象变为27，等于27==target，返回true；

如果找到最左或最下仍然不匹配，终止寻找，返回false

编写程序  
C++版本

class Solution \{  
public:  
    bool Find(int target, vector<vector<int> > array) \{  
        int row = array.size();  
        int col = array\[0\].size();  
        int i = 0;  
        int j = col-1;  
        while(i<row && j>=0)  
        \{  
            if (array\[i\]\[j\] == target)  
                return true;  
            if (array\[i\]\[j\] > target)  
                j--;  
            if (array\[i\]\[j\] < target)  
                i++;  
        \}  
        return false;  
    \}  
\};  
  
Java版本

public class Solution \{  
    public boolean Find(int target, int \[\]\[\] array) \{  
        int row = array.length;  
        int col = array\[0\].length;  
        int i = 0;  
        int j = col-1;  
        while(i<row && j>=0)\{  
            if(array\[i\]\[j\] < target)  
                i++;  
            else if(array\[i\]\[j\] > target)  
                j--;  
            else  
                return true;  
        \}  
        return false;  
    \}  
\}  
  
python版本

\# -\*- coding:utf-8 -\*-  
class Solution:  
    \# array 二维列表  
    def Find(self, target, array):  
        \# write code here  
        row = len(array)  
        col= len(array\[0\])  
        i = 0  
        j = col-1  
        while i<row and j>=0:  
            if array\[i\]\[j\] < target:  
                i += 1  
            elif array\[i\]\[j\] > target:  
                j -= 1  
            else:  
                return True  
        return False  
  
【附】vector基本操作  
(1)头文件 \#include<vector>.

(2)创建vector对象 vector<int> vec;。vector的元素不仅仅可以是int,double,string,还可以是结构体

(3)尾部插入数字：vec.push\_back(a);

(4)使用下标访问元素，cout<<vec\[0\]<<endl;，记住下标是从0开始的。

(5)使用迭代器访问元素.

vector<int>::iterator it;

for(it=vec.begin();it!=vec.end();it++)

cout<<\*it<<endl;  
  
(6)插入元素：

vec.insert(vec.begin()+i,a);//在第i+1个元素前面插入a;  
  
(7)删除元素：

vec.erase(vec.begin()+2);//删除第3个元素

vec.erase(vec.begin()+i,vec.end()+j);//删除区间\[i,j-1\];区间从0开始  
  
(8)大小 vec.size();(二维vector矩阵的列数：vec\[0\].size();)

(9)清空 vec.clear();

常见算法：   
需要头文件 \#include<algorithm>