当前位置:网站首页>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};
}
};
边栏推荐
- Unity3d interface is embedded in WPF interface (mouse and keyboard can respond normally)
- Oracle installation enhancements error
- flex弹性布局
- Mysql database transaction learning notes
- Implementation of corner badge of Youmeng message push
- Netease cloud wechat applet
- The configuration and options of save actions are explained in detail, and you won't be confused after reading it
- Confitest of fixture py
- 信息安全实验三 :PGP邮件加密软件的使用
- Variable parameter of variable length function
猜你喜欢
信息安全实验一:DES加密算法的实现
How to speed up video playback in browser
Jenkins automated email
【BW16 应用篇】安信可BW16模组/开发板AT指令实现MQTT通讯
Variable parameter of variable length function
Network request process
VSCode+mingw64+cmake
信息安全实验四:Ip包监视程序实现
Information Security Experiment 2: using x-scanner scanning tool
Huawei HCIP - datacom - Core 03 jours
随机推荐
Install pyqt5 and Matplotlib module
正则匹配以XXX开头的,XXX结束的
Unity3d interface is embedded in WPF interface (mouse and keyboard can respond normally)
MongoDB怎么实现创建删除数据库、创建删除表、数据增删改查
印象笔记终于支持默认markdown预览模式
[SVN] what is SVN? How do you use it?
Locust performance test 2 (interface request)
Sublime Text4 download the view in bower and set the shortcut key
Jenkins+ant+jmeter use
沙龙预告|GameFi 领域的瓶颈和解决方案
Pytest+request+allure+excel interface automatic construction from 0 to 1 [five nails / flying Book notice]
Unity shader (to achieve a simple material effect with adjustable color attributes only)
Netease cloud wechat applet
Pick up the premise idea of programming
进程间的通信方式
Run can start normally, and debug doesn't start or report an error, which seems to be stuck
Locust performance test 5 (analysis)
Information Security Experiment 4: implementation of IP packet monitoring program
Final keyword
(3/8)枚举的不当用法 之 方法参数(二)