当前位置:网站首页>Leetcode 74. Search two-dimensional matrix
Leetcode 74. Search two-dimensional matrix
2022-04-23 20:26:00 【Die in a trap】
74、 Search for a two-dimensional matrix
1) Title Description
Write an efficient algorithm to judge m x n
Matrix , Is there a target value . The matrix has the following characteristics :
- The integers in each row are arranged in ascending order from left to right .
- The first integer in each row is greater than the last integer in the previous row .
Example 1:
Input :matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output :true
Example 2:
Input :matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output :false
Tips :
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-10^4 <= matrix[i][j], target <= 10^4
2) analysis
Traveled through , Intra bank dichotomy .
- From the title, we can see , Traverse the matrix first by row , Matrix elements are non decreasing . Then, if the target value is less than the matrix row, traverse the first element first or greater than the last element , The target value must no longer be in the matrix ;
- If the target value may be in the matrix , Then traverse each row of the matrix , Compare the target value with the last element of the current row , Judge whether the target value may be in the current line ;
- If the target value is in the current line , Search the subscript of the corresponding element by dichotomy ;
- Judge whether the element corresponding to the searched subscript is equal to the target value .
3)C++
Code
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix[0][0]>target||matrix[matrix.size()-1][matrix[0].size()-1]<target)
return false;
int m=matrix.size();
int n=matrix[0].size();
for(int i=0;i<m;i++){
if(matrix[i][n-1]<target)
continue;
else{
int left=0;
int right=n-1;
while(left<=right){
int mid=(left+right)/2;
if(matrix[i][mid]<target)
left=mid+1;
else
right=mid-1;
}
return matrix[i][left]==target;
}
}
return false;
}
};
版权声明
本文为[Die in a trap]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204232023107701.html
边栏推荐
- Operation of numpy array
- 考研英语唐叔的语法课笔记
- Scrapy教程 - (2)寫一個簡單爬蟲
- JDBC tool class jdbcconutil gets the connection to the database
- go-zero框架数据库方面避坑指南
- Numpy - creation of data type and array
- How about CICC fortune? Is it safe to open an account
- Historical track data reading of Holux m1200-e Bluetooth GPS track recorder
- Handwritten Google's first generation distributed computing framework MapReduce
- [graph theory brush question-4] force deduction 778 Swimming in a rising pool
猜你喜欢
SQL Server Connectors By Thread Pool | DTSQLServerTP plugin instructions
16MySQL之DCL 中 COMMIT和ROllBACK
Latest investigation and progress of building intelligence based on sati
What is the difference between a host and a server?
Devexpress 14.1 installation record
selenium. common. exceptions. WebDriverException: Message: ‘chromedriver‘ executable needs to be in PAT
[PTA] get rid of singles
波场DAO新物种下场,USDD如何破局稳定币市场?
Actual measurement of automatic ticket grabbing script of barley network based on selenium (the first part of the new year)
[target tracking] pedestrian attitude recognition based on frame difference method combined with Kalman filter, with matlab code
随机推荐
PCL点云处理之直线与平面的交点计算(五十三)
R language uses the preprocess function of caret package for data preprocessing: BoxCox transform all data columns (convert non normal distribution data columns to normal distribution data and can not
Livego + ffmpeg + RTMP + flvjs to realize live video
LeetCode 232、用栈实现队列
Error reported by Azkaban: Azkaban jobExecutor. utils. process. ProcessFailureException: Process exited with code 127
Implementation of mypromise
LeetCode 20、有效的括号
Investigate why close is required after sqlsession is used in mybatties
Commit and rollback in DCL of 16 MySQL
Install MySQL 5.0 under Linux 64bit 6 - the root password cannot be modified
Use the rolling division method to find the maximum common divisor of two numbers
Actual measurement of automatic ticket grabbing script of barley network based on selenium (the first part of the new year)
[latex] 5 how to quickly write out the latex formula corresponding to the formula
【栈和队列专题】—— 滑动窗口
An error is reported when sqoop imports data from Mysql to HDFS: sqlexception in nextkeyvalue
The second method of file upload in form form is implemented by fileitem class, servletfileupload class and diskfileitemfactory class.
上海回應“面粉官網是非法網站”:疏於運維被“黑”,警方已立案
Leetcode dynamic planning training camp (1-5 days)
Operation of numpy array
Recommend an open source free drawing software draw IO exportable vector graph