当前位置:网站首页>第一讲:寻找矩阵的极小值
第一讲:寻找矩阵的极小值
2022-07-07 06:51:00 【奋斗吧!骚年!】
题目:AcWing 1452. 寻找矩阵的极小值
给定一个 n×n 的矩阵,矩阵中包含 n×n 个 互不相同 的整数。
定义极小值:如果一个数的值比与它相邻的所有数字的值都小,则这个数值就被称为极小值。
一个数的相邻数字是指其上下左右四个方向相邻的四个数字,另外注意,处于边界或角落的数的相邻数字可能少于四个。
要求在 O(nlogn) 的时间复杂度之内找出任意一个极小值的位置,并输出它在第几行第几列。
本题中矩阵是隐藏的,你可以通过我们预设的 int 函数 query 来获得矩阵中某个位置的数值是多少。
例如,query(a,b) 即可获得矩阵中第 a 行第 b 列的位置的数值。
注意:
矩阵的行和列均从 0 开始编号。
query()函数的调用次数不能超过 (n+2)×⌈log2n⌉+n。
答案不唯一,输出任意一个极小值的位置即可。
数据范围
1≤n≤300,矩阵中的整数在int范围内。
输入样例:
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
输出样例:
[0, 0]
题目分析:
第一种想到的方式就是从起点开始找比自己小的点,一直找,那么我们肯定会找到极小值(因为点各不相同)
但是最坏情况就是访问n2次。
第二种就是二分的方法,先在中间列找出最小值,然后看左右两边
1.如果 v<l,v<r那么v就是极小值
2.如果 l<v,那么左边有极小值
3.如果 r<v,那么右边有极小值
为什么呢?
假设右边 r<v,那么中间mid这一列都比r要大,那么我们用第一种方法寻找肯定不可能穿过mid这一列(因为会寻找比r小的数),那么在mid右边肯定有极小值,这样减少了一半的寻找量,如此反复最后就会找到。
// 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) // 二分法
{
int mid = l + r >> 1;
LL val=INF;
int k=0; // 保存哪一行最小
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; // 查询左边
LL right=mid+1<n?query(k,mid+1):INF; // 查询右边
if(val<left&&val<right)return {
k,mid}; // 如果当前点是最小值
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};
}
};
边栏推荐
- 数据建模中利用3σ剔除异常值进行数据清洗
- What is the rating of Huishang futures company? Is it safe to open an account? I want to open an account, OK?
- golang select机制和超时问题怎么解决
- Difference between interface iterator and iteratable
- Variable parameter of variable length function
- MySql数据库-索引-学习笔记
- ComputeShader
- Postman interface test (I. installation and use)
- Unity uses mesh to realize real-time point cloud (I)
- STM32 and motor development (from stand-alone version to Networking)
猜你喜欢
The configuration and options of save actions are explained in detail, and you won't be confused after reading it
Network request process
MySql数据库-索引-学习笔记
Summary of PMP learning materials
Information Security Experiment 1: implementation of DES encryption algorithm
Regular matching starts with XXX and ends with XXX
Difference between interface iterator and iteratable
Kubernetes cluster capacity expansion to add node nodes
答案在哪里?action config/Interceptor/class/servlet
其实特简单,教你轻松实现酷炫的数据可视化大屏
随机推荐
[SVN] what is SVN? How do you use it?
The configuration and options of save actions are explained in detail, and you won't be confused after reading it
Storage of data in memory
Jenkins modifies the system time
STM32 clock system
Interface test API case, data and interface separation
4、 Fundamentals of machine learning
Pytest installation (command line installation)
Mysql数据库-锁-学习笔记
Oracle安装增强功能出错
Information Security Experiment 2: using x-scanner scanning tool
STM32 and motor development (from stand-alone version to Networking)
Jenkins+ant+jmeter use
Windows starts redis service
二叉树高频题型
PMP experience learning and sharing process
asp. How to call vb DLL function in net project
C language pointer (Part 2)
華為HCIP-DATACOM-Core_03day
Some pit avoidance guidelines for using Huawei ECS