首页 > 代码库 > [LeetCode] Search a 2D Matrix
[LeetCode] 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.
Hide Tags
Array Binary Search在一个矩阵中确定是否存在某个数，这个矩阵有规律：一个排序好的数组，一行一行地填入矩阵。解题思路就是先二分查找会在哪一行，然后二分查找找是否存在。
#include<iostream>#include<vector>using namespace std;class Solution {public: bool searchMatrix(vector<vector<int> > &matrix, int target) { int m=matrix.size(); if(m<1) return false; int n=matrix[0].size(); int tm;//cout<<"m:"<<m<<" n:"<<n<<endl; if(m==1) tm=0; else{ if(matrix[m-1][0]<=target) tm=m-1; else{ int lft=0,rgt=m-1; tm =0; do{ if(matrix[tm+1][0]>target) break; int mid = (lft+rgt)/2; if(matrix[mid][0]>target) rgt=mid; else lft=mid; tm = lft; }while(lft+1<rgt); } } int lft=0,rgt=n-1; if(matrix[tm][rgt]==target||matrix[tm][lft]==target) return true; if(matrix[tm][rgt]<target) return false; int tn=lft; do{ int mid=(lft+rgt)/2; if(matrix[tm][mid]>target) rgt = mid; else lft=mid; tn = lft; if(matrix[tm][tn]==target) return true; }while(lft+1<rgt); return false; }};int main(){ vector<vector<int> > matrix{{1, 3, 5, 7},{10, 11, 16, 20},{23, 30, 34, 50}}; Solution sol; cout<<sol.searchMatrix(matrix,2)<<endl; return 0;}
[LeetCode] Search a 2D Matrix
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。