有序矩阵中查找，横竖各自有序的二维数组

本文主要是介绍有序矩阵中查找，横竖各自有序的二维数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、描述

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

示例:

现有矩阵 matrix 如下：

[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]

来源：力扣（LeetCode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
同一个题链接

2、关键字

二维数组，横竖各自有序，查找

3、思路

暴力一次遍历去搜索，面试肯定挂！，所以以后练手也看会不会，如果有更好的方法就直接不必写这个了。
思路二：有序马上想到二分，但是还有点麻烦
思路三：逆时针旋转矩阵45度，发现变成了类似平衡二叉树，左边的都小，右边的都大，使用两个标志位：左下角，和右上角。
如果左下角比target更大：则左下角标志位的此一行不必再考虑。因为右边的更大，执行 i --,（i 初始化为行数 - 1）
如果右上角的比target更大，则右上角标志位所在的列不必再考虑，执行j ++ (j初始化为0）
如果存在就会在未达到边界条件之前结束循环，如果达到边界跳出循环就说明不存在。
初始化到左下角位置，然后寻找

4、nodes

1、也不是每次有序就二分了
2、

5、复杂度

时间：O(n + m)
空间：O(1)

6、code

class Solution {
public:bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {int n = matrix.size();if(n ==0) return false;int m = matrix[0].size();if(m == 0) return 0;int i = n - 1;int j = 0;while(i >= 0 && j < m){  // 如果调跳出边界，就是没找到if(matrix[i][j] > target) i--;else if(matrix[i][j] < target) j++;elsereturn true;  // 找到了}return false;}
};

这篇关于有序矩阵中查找，横竖各自有序的二维数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---