LeetCode *** 74. Search a 2D Matrix

本文主要是介绍LeetCode *** 74. Search a 2D Matrix，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[[1,   3,  5,  7],[10, 11, 16, 20],[23, 30, 34, 50]
]

Given target = 3, return true.

分析：

分治。

代码：

class Solution {
public:int myt;bool searchMatrix(vector<vector<int>>& matrix, int target) {if(matrix.size()<1)return false;myt=target;return search(matrix,0,matrix.size()-1,0,matrix[0].size()-1);}bool search(vector<vector<int>>& matrix,int i1,int i2,int j1,int j2){if(matrix[i1][j1]>myt)return false;if(i1>i2||j1>j2)return false;if(i1==i2&&j1==j2){if(matrix[i1][j1]==myt)return true;else return false;}if(i1!=i2){int midi=(i1+i2)/2;if(matrix[midi][j2]<myt) return search(matrix,midi+1,i2,j1,j2);else return search(matrix,i1,midi,j1,j2);}else {int midj=(j1+j2)/2;if(matrix[i1][midj]<myt) return search(matrix,i1,i2,midj+1,j2);else return search(matrix,i1,i2,j1,midj);}}
};

这篇关于LeetCode *** 74. Search a 2D Matrix的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---