本文主要是介绍LeetCode *** 240. Search a 2D Matrix II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
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 in ascending from left to right.
- Integers in each column are sorted in ascending from top to bottom.
For example,
Consider the following 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] ]
Given target = 5, return true.
Given target = 20, return false.
分析：
分治+二分搜索
代码：
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){if(matrix[i1][j1]==myt)return true;else return false;}int midi=(i1+i2)/2;int midj=(j1+j2)/2;if(matrix[midi][midj]<myt){if(midi<i2&&midj<j2)return search(matrix,midi+1,i2,midj+1,j2)||search(matrix,i1,midi,midj+1,j2)||search(matrix,midi+1,i2,j1,midj);else if(midi<i2)return search(matrix,midi+1,i2,j1,midj);else if(midj<j2)return search(matrix,i1,midi,midj+1,j2);}else {if(midi<i2&&midi>i1&&midj>j1&&midj<j2)return search(matrix,i1,midi,j1,midj)||search(matrix,midi+1,i2,j1,midj-1)||search(matrix,i1,midi-1,midj-1,j2);else if(midi<i2&&midj>j1)return search(matrix,i1,midi,j1,midj)||search(matrix,midi+1,i2,j1,midj-1);else if(midi>i1&&midj<j2)return search(matrix,i1,midi,j1,midj)||search(matrix,i1,midi-1,midj-1,j2);else return search(matrix,i1,midi,j1,midj);}}
};这篇关于LeetCode *** 240. Search a 2D Matrix II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
