当前位置:网站首页>Lesson 1: finding the minimum of a matrix
Lesson 1: finding the minimum of a matrix
2022-07-07 09:32:00 【Fight! Sao Nian!】
subject :AcWing 1452. Find the minimum of the matrix
Given a n×n Matrix , The matrix contains n×n individual Different from each other The integer of .
Define the minimum : If the value of a number is smaller than that of all adjacent numbers , Then this value is called the minimum .
The adjacent numbers of a number refer to the four adjacent numbers in the upper, lower, left and right directions , Also note , The number at the boundary or corner may have less than four adjacent numbers .
Ask for in O(nlogn) Find the position of any minimum within the time complexity , And output its rows and columns .
The matrix in this question is hidden , You can use our preset int function query To get the value of a certain position in the matrix .
for example ,query(a,b) You can get the... In the matrix a Xing di b The value of the position of the column .
Be careful :
The rows and columns of the matrix are from 0 Numbered starting .
query() Function cannot be called more than (n+2)×⌈log2n⌉+n.
The answer is not unique , Output the position of any minimum value .
Data range
1≤n≤300, The integers in the matrix are int Within the scope of .
sample input :
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
sample output :
[0, 0]
Topic analysis :
The first way to think about it is to start from the starting point and find something smaller than yourself , Keep looking for , Then we will definitely find the minimum ( Because the points are different )
But the worst case is to visit n2 Time .
The second method is dichotomy , First find the minimum value in the middle column , Then look at the left and right
1. If v<l,v<r that v Is the minimum
2. If l<v, Then there is a minimum on the left
3. If r<v, Then there is a minimum on the right
Why? ?
Suppose the right r<v, So in the middle mid This column is better than r Be big , Then we use the first method to find that it is definitely impossible to cross mid This column ( Because I will look for something better than r Small number ), So in mid There must be a minimum on the right , This reduces the amount of search by half , Such repetition will finally find .
// Forward declaration of queryAPI.
// int query(int x, int y);
// return int means matrix[x][y].
class Solution {
public:
vector<int> getMinimumValue(int n) {
typedef long long LL;
const LL INF = 1e15;
int l=0,r=n-1;
while(l<r) // Dichotomy
{
int mid = l + r >> 1;
LL val=INF;
int k=0; // Which row to save is the smallest
for(int i=0;i<n;i++)
{
int t=query(i,mid);
if(t<val)
{
val=t;
k=i;
}
}
LL left=mid?query(k,mid-1):INF; // Query left
LL right=mid+1<n?query(k,mid+1):INF; // Query the right
if(val<left&&val<right)return {
k,mid}; // If the current point is the minimum
else if(left<val)r=mid-1;
else l=mid+1;
}
int k;
LL val=INF;
for(int i=0;i<n;i++)
{
int t=query(i,l);
if(t<val)
{
val=t;
k=i;
}
}
return {
k,l};
}
};
边栏推荐
- Unity shader (learn more about vertex fragment shaders)
- Huawei hcip datacom core_ 03day
- nlohmann json
- Information Security Experiment 2: using x-scanner scanning tool
- Data association between two interfaces of postman
- Sublime Text4 download the view in bower and set the shortcut key
- Pytest+request+allure+excel interface automatic construction from 0 to 1 [familiar with framework structure]
- Locust performance test 3 (high concurrency, parameter correlation, assembly point)
- MySql数据库-索引-学习笔记
- Unity shader (basic concept)
猜你喜欢
Locust performance test 2 (interface request)
How to use clipboard JS library implements copy and cut function
【BW16 应用篇】安信可BW16模组/开发板AT指令实现MQTT通讯
信息安全实验三 :PGP邮件加密软件的使用
Nested (multi-level) childrn routes, query parameters, named routes, replace attribute, props configuration of routes, params parameters of routes
12、 Sort
Regular matching starts with XXX and ends with XXX
【SVN】SVN是什么?怎么使用?
Jemter operation
Mysql database lock learning notes
随机推荐
Pick up the premise idea of programming
Information Security Experiment 2: using x-scanner scanning tool
软件建模与分析
Niuke - Huawei question bank (61~70)
# Arthas 简单使用说明
Mysql database index study notes
Unity shader (pass user data to shader)
Huawei HCIP - datacom - Core 03 jours
四、机器学习基础
战略合作|SubQuery 成为章鱼网络浏览器的秘密武器
数据库多表关联查询问题
MongoDB怎么实现创建删除数据库、创建删除表、数据增删改查
Jemter operation
Detailed learning notes of JVM memory structure (I)
Binary tree high frequency question type
Jmeters use
Oracle installation enhancements error
Information Security Experiment 4: implementation of IP packet monitoring program
DRF defines views and routes
VSCode+mingw64