【算法】【数组与矩阵模块】在排好序的矩阵中找数，时间复杂度O(M+N)

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
给定二维数组arr，arr为排好序的数组，其中arr同时满足，从左到右递增，从上到下递增，给定一个数k，在尽可能少的时间内找到数k即可
如：
arr = $\left[\begin{array}{cccc}0& 1& 2& 5\\ 2& 3& 4& 7\\ 4& 4& 4& 8\\ 5& 7& 7& 9\end{array}\right]$
k = 7
结果：true

解决方案

原问题：
假设arr为N*M的矩阵
1、从右上角或者左下角开始，如果k < arr[N][0] ，说明k一定小于arr的第N行，行–
2、如果k > arr[N][0] ,说明k一定大于arr的第0列，列++
3、通过以上规则，查找到数后返回true，找不到并且越界后则退出循环，返回false

代码编写

java语言版本

原问题：

/*** 二轮测试：在排好序的矩阵中找数* @param arr* @param k* @return*/public static boolean isContainsCp1(int[][] arr, int k) {if (arr == null || arr.length == 0) {return false;}int row = arr.length - 1;int col = 0;while (row >= 0 && col <= arr[0].length - 1) {int cur = arr[row][col];if (cur == k) {return true;}else if (cur > k) {// 当前行不会存在krow--;}else {// 当前列不会存在kcol++;}}return false;}public static void main(String[] args) {System.out.println(isContainsCp1(new int[][]{{0,1,2,5},{2,3,4,7},{4,4,4,8},{5,7,7,9}}, 7));}

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

每一次的比较都能够至少排除一行或者一列，这个速度应该是比较快的了，如果大家有更好的办法记得评论区各显神通哦~

写在最后

方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
如果需要git源码可邮件给[e-mail]
再次感谢左大神对我算法的指点迷津！