网站开发计划书封面设计,软件开发报价,wordpress文章删除,百度统计平台吉大21级算法分析与设计的一道大题#xff0c;由于每一行都是排好序的直接逐行二分 可以达到#xff1a;O(mlogn)。但是这里追求更广的思路可以使用其他方法。 矩阵四分#xff1a; 在矩阵中用中心点比较#xff0c;如果target大于中心点的值#xff0c;则由于升序排列由于每一行都是排好序的直接逐行二分 可以达到O(mlogn)。但是这里追求更广的思路可以使用其他方法。 矩阵四分 在矩阵中用中心点比较如果target大于中心点的值则由于升序排列以中心点为右下角的小矩阵就不用再查找了因为他们一定比target小。剩下三个矩形都可能比中心点大因此在剩下三个矩阵中继续查找如果target小于中心点以中心点为右下角的小矩阵可能包含并且中心点的左下方和右上方都有可能比中心点小因此仍然需要继续查找。 每次可以去掉矩阵中的¼对于每一个小矩阵它们是整个矩阵的¼分析如下 class Solution {
public:bool searchMatrix(vectorvectorint matrix, int target) {tartarget;return find(matrix,0,matrix.size()-1,0,matrix[0].size()-1);}
private:bool find(vectorvectorint matrix,int row_left,int row_right,int col_top,int col_bottom){if(row_leftrow_right||col_topcol_bottom||col_bottommatrix[0].size()||row_rightmatrix.size()) return false;if(row_leftrow_rightcol_topcol_bottomtar!matrix[row_left][col_bottom]) return false;int mid_row(row_leftrow_right)1;int mid_col(col_topcol_bottom)1;if(tarmatrix[mid_row][mid_col]) return true;if(tarmatrix[mid_row][mid_col])return find(matrix,mid_row1,row_right,col_top,mid_col)||find(matrix,row_left,mid_row,mid_col1,col_bottom)||find(matrix,mid_row1,row_right,mid_col1,col_bottom);else return find(matrix,row_left,mid_row,col_top,mid_col)||find(matrix,mid_row1,row_right,col_top,mid_col)||find(matrix,row_left,mid_row,mid_col1,col_bottom);}
private:int tar;
};
Z字形查找
Krahets - 力扣LeetCode 用二叉树来看就特别清晰了。任何一个结点均满足左儿子小于它右儿子大于它。如果target比它大同一行左边一定不再满足要求如果target比它小同一列下边一定不再满足要求。由于我们是从右上角开始的依次进行每一步都使得解只能在划定的范围内因此这样做是正确的时间复杂度为O(mn)。 class Solution {
public:bool searchMatrix(vectorvectorint matrix, int target) {int m0,nmatrix[0].size()-1;while(mmatrix.size()n0matrix[m][n]!target){if(matrix[m][n]target) --n;else m;}coutm n;if(mmatrix.size()n0) return true;return false;}
};
暴力解法 防止题目做多了不会暴力了 class Solution {
public:bool searchMatrix(vectorvectorint matrix, int target) {for(int i0;imatrix.size();i)for(int num:matrix[i])if(numtarget) return true;return false;}
};
