面试金典--11.6

题目描述：数组每行每列都是有序的，编写代码找到指定元素

思路：

（1）从数组右上角开始找，每次更新i,j（已经实现）

（2）对每个元素，它必定是它右下角子二维数组的最小值，也必定是左上角子二维数组的最大值，这样可以减少规模，没有实现

 1 #include <iostream>
 2 #include <queue>
 3 #include <climits>
 4 #include <algorithm>
 5 #include <memory.h>
 6 #include <stdio.h>
 7 #include <ostream>
 8 #include <vector>
 9 #include <list>
10 #include <cmath>
11 #include <string>
12 #include <stdexcept>
13 #include <stack>
14 #include <map>
15 using namespace std;
16 
17 pair<int,int> fun(vector<vector<int> > a,int target)
18 {
19     if(a.size() == 0)
20     {
21         return make_pair(-1,-1);
22     }
23     int m = a.size();
24     int n = a[0].size();
25     int i = 0;
26     int j = n-1;
27     while(i < m && j >= 0)
28     {
29         if(a[i][j] == target)
30         {
31             return make_pair(i,j);
32         }
33         else if(a[i][j] > target)
34         {
35             --j;
36         }
37         else
38         {
39             ++i;
40         }
41     }
42     return make_pair(-1,-1);
43 }
44 
45 int main()
46 {
47     vector<vector<int> > a;
48     vector<int> l1;
49     l1.push_back(1);
50     l1.push_back(2);
51     a.push_back(l1);
52     l1.clear();
53     l1.push_back(3);
54     l1.push_back(4);
55     a.push_back(l1);
56 
57     pair<int,int> res = fun(a,3);
58     cout<<res.first<<" "<<res.second<<endl;
59     return 0;
60 }