二维数组中查找问题

    xiaoxiao2021-03-25  19

    给定一个M*N的二维数组,在每行、或者每列上的元素都是按升序排列的(从小到大),既:matrix[i][j]<matrix[i][j+1];matrix[i][j]<matrix[i+1][j]

    要求设计一个算法,在矩阵中查找是否存在给定的值(target)

    因为这是一个每行每列的矩阵,我们很快就想到可以对每一行或者每一列进行二分查找,看target是否存在于二维数组中,对M*N二维矩阵,

    此算法复杂度为O(M*logN),很容易写出以下代码:

    #include <iostream> #include <vector> #include <algorithm> using namespace std; bool findtarget(vector<vector<int> >& matrix, int target){ int m = matrix[0].size() ; int n = matrix.size(); for(int i = 0;i < n;i++){ if(binary_search(matrix[i].begin() ,matrix[i].end(),target)){ //运用STL中的二分查找函数 return true; } } return false; } int main() { int m,n; cin>>m>>n; vector<vector<int> > a; vector<int> line; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ int num; cin>>num; line.push_back(num); } a.push_back(line); } int target; while (1){ cin>>target; bool iffindtarget = findtarget(a,target); if(iffindtarget){ cout<<"true"<<endl; } else{ cout<<"false"<<endl; } } return 0; }    如果不注意的话,很多人一开始会侮辱一个陷阱,设计一个错误的算法:先对行(列)进行二分查找,再对列(行)进行二分查找。既如果目标元素落入第一行(列)的两个元素之间,那么目标元素在两列中小的那列,如果不在,就查找失败。 14  7  11152  5 81219369162210131417241821232630 比如我要查找13是否在矩阵中,先对第一行扫描,13介于11和15之间,则对第四列扫描,13不在第四列中,查找失败。

    这很明显发生了错误。

    另外一种解法是对斜对角线进行扫描,从右上角开始,每走一步往左或往下,历遍对角线可以一次排除一行或一列,复杂度在O(M+N),代码实现如下:

    bool searchMatrix(vector<vector<int>>& matrix, int target) { int m = matrix.size(); if (m == 0) return false; int n = matrix[0].size(); int i = 0, j = n - 1; while (i < m && j >= 0) { if (matrix[i][j] == target) return true; else if (matrix[i][j] > target) { j--; } else i++; } return false; }

    转载请注明原文地址: https://ju.6miu.com/read-50440.html

    最新回复(0)