title: 寻找矩阵的极小值
date: 2023-07-24 20:44:49
tags:
- c/c++
categories:
- 算法
- 笔试
top:
寻找矩阵的极小值
题目来自acwing
题目（点击跳转）
给定一个 n×n的矩阵，矩阵中包含 n×n个 互不相同 的整数。
定义极小值：如果一个数的值比与它相邻的所有数字的值都小，则这个数值就被称为极小值。
一个数的相邻数字是指其上下左右四个方向相邻的四个数字，另外注意，处于边界或角落的数的相邻数字可能少于四个。
要求在 O(nlogn) 的时间复杂度之内找出任意一个极小值的位置，并输出它在第几行第几列。
本题中矩阵是隐藏的，你可以通过我们预设的 int 函数 query来获得矩阵中某个位置的数值是多少。
例如，query(a,b) 即可获得矩阵中第 a行第 b 列的位置的数值。
注意：
- 矩阵的行和列均从 00 开始编号。
query()函数的调用次数不能超过 (n+2)×⌈log2n⌉+n。- 答案不唯一，输出任意一个极小值的位置即可。
数据范围
1≤n≤300，矩阵中的整数在int范围内。
输入样例：
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
输出样例：
[0, 0]
思路：
二分
题目的意思是一个n*n的矩阵，里面每一个数都是互不相同的且都在int范围内，要找到一个极小值（这里答案不唯一），任意一个合法答案即可。这里极小值的定义就是小于和它相邻的任意一个数，如果在边上，那就是小于其他的数。
解法的话，就是使用二分，对矩阵的列进行二分，首先取出中间的一列，从上到小遍历出这一列的最小值，找到这个位置后，取出它左边和右边相邻的元素，然后进行比较
- 如果左边和右边的元素都大于它，那么这个位置就是一个合法的答案。
- 如果左边小于它，那么在左边的区域肯定可以找到一个合法的答案。
- 这里可以描述一下，就是中间一列的最小值，然后左边的元素小于它，那么就可以顺着左侧元素开始找，不管如何找，不会穿过中间这一列到右边，所以左侧一定可以找到一个答案，那同理，右侧也是一样的。
- 如果右边小于它，那么在右边的区域肯定也可以找到一个合法的答案。
假设这里左侧元素小，那么将左侧的二分之n列再进行二分，重复上面的操作，又可以将二分之n列分为二分之一，最后找到一列，在这一列上找到最小的值就是合法的极小值。
代码：
// 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;
// 定义左边界和右边界
int l = 0, r = n - 1;
// 定义一个最大的数，方便在一列中寻找最小值时对变量进行初始化
const int INF = 0x3f3f3f3f;
// 二分列
while(l < r) {
// 取出列的中间一列,然后循环找到这一列的最小值
int mid = (l + r) / 2;
int k;
int val = INF;
for(int i = 0; i < n; i ++ ) {
int t = query(i, mid);
if(val > t) {
val = t;
k = i;
}
}
// 找到最小值即为[k,mid]，取出左右两边的元素，如果出界就为INF
int left = mid ? query(k, mid - 1) : INF;
int right = mid + 1 < n ? query(k, mid + 1) : INF;
// 进行比较
if(val < left && val < right) return {k, mid};
if(val > left) r = mid - 1;
else l = mid + 1;
}
// 次数L = R，也就是找到了答案所在的一列，进行遍历比较得出最小的数即为一个合法答案
int k;
int val = INF;
for(int i = 0; i < n; i ++ ) {
int t = query(i, r);
if(val > t) {
val = t;
k = i;
}
}
return {k, r};
}
};