C++刷剑指offer（面试题04. 二维数组中的查找）【vector<vector<int>>】

糖逗

题目描述：

1. 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
   
2. 
   
3. &#160;
   
4. 
   
5. 示例:
   
6. 
   
7. 现有矩阵 matrix 如下：
   
8. 
   
9. [
   
10.   [1,   4,  7, 11, 15],
    
11.   [2,   5,  8, 12, 19],
    
12.   [3,   6,  9, 16, 22],
    
13.   [10, 13, 14, 17, 24],
    
14.   [18, 21, 23, 26, 30]
    
15. ]
    
16. 给定 target&#160;=&#160;5，返回&#160;true。
    
17. 
    
18. 给定&#160;target&#160;=&#160;20，返回&#160;false。
    
19. 
    
20. &#160;
    
21. 
    
22. 限制：
    
23. 
    
24. 0 <= n <= 1000
    
25. 
    
26. 0 <= m <= 1000
    
27. 
    
28. 来源：力扣（LeetCode）
    
29. 链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
    
30. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. #include <vector>
   
2. #include <iostream>
   
3. 
   
4. using namespace std;
   
5. 
   
6. bool solution(vector<vector<int> >& input, int target){
   
7.         if(input.size() == 0 || input[0].size() == 0) return false;
   
8.         //start point
   
9.         int a = input.size() - 1;
   
10.         int b = 0;
    
11.         while(a >= 0 && b <= input[0].size()-1){
    
12.         if(input[a][b] == target) return true;
    
13.                 if(input[a][b] > target){
    
14.                          a--;
    
15.                         continue;}
    
16.                 if(input[a][b] < target) {
    
17.                         b++;
    
18.                         continue;}
    
19.         }
    
20.         return false;       
    
21. }       
    
22. int main(void){
    
23.         vector<vector<int> > input;
    
24.         int n, m;
    
25.         cout << "please send a number for row" << endl;
    
26.         cin >> n;
    
27.         input.resize(n);
    
28.         cin.clear();
    
29.         cout << "please send a number for column" << endl;
    
30.         cin >> m;
    
31.         cin.clear();
    
32.         cout << "please send number for matrix(n*m)" << endl;
    
33.         int number;
    
34.         for(int i = 0; i < n; i++){
    
35.                 for(int j = 0; j < m; j++){
    
36.                         cin >> number;
    
37.                         input[i].push_back(number);
    
38.                 }
    
39.         }
    
40.         for(int i = 0; i < n; i++){
    
41.                 for(int j = 0; j < m; j++){
    
42.                         cout << input[i][j] << " ";
    
43.                 }
    
44.                 cout << endl;
    
45.         }
    
46.         cout << endl;
    
47.         cin.clear();
    
48.         int target;
    
49.         cin >> target;
    
50.         bool result = solution(input, target);
    
51.         cout << result << endl;
    
52.         return 0;
    
53. }

复制代码

参考链接：https://www.bilibili.com/video/B ... 6509475985055900873
https://bbs.csdn.net/topics/392144947

注意事项：
1.边界的确定
2.while（）里的条件如果把符号全部换成！=则存在遗漏情况的问题。
3.从矩阵的右上角或左下角开始作为初始点。