寻找矩阵的极小值

题目来自acwing

题目（点击跳转）

给定一个 n×n的矩阵，矩阵中包含 n×n个 互不相同 的整数。

定义极小值：如果一个数的值比与它相邻的所有数字的值都小，则这个数值就被称为极小值。

一个数的相邻数字是指其上下左右四个方向相邻的四个数字，另外注意，处于边界或角落的数的相邻数字可能少于四个。

要求在 O(nlogn) 的时间复杂度之内找出任意一个极小值的位置，并输出它在第几行第几列。

本题中矩阵是隐藏的，你可以通过我们预设的 int 函数 query来获得矩阵中某个位置的数值是多少。

例如，query(a,b) 即可获得矩阵中第 a行第 b 列的位置的数值。

注意：

  1. 矩阵的行和列均从 00 开始编号。
  2. query()函数的调用次数不能超过 (n+2)×⌈log2n⌉+n。
  3. 答案不唯一，输出任意一个极小值的位置即可。

数据范围

1≤n≤300，矩阵中的整数在int范围内。

输入样例：

1
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]

输出样例：

1
[0, 0]

思路：

二分

题目的意思是一个n*n的矩阵，里面每一个数都是互不相同的且都在int范围内，要找到一个极小值（这里答案不唯一），任意一个合法答案即可。这里极小值的定义就是小于和它相邻的任意一个数，如果在边上，那就是小于其他的数。

解法的话，就是使用二分，对矩阵的列进行二分，首先取出中间的一列，从上到小遍历出这一列的最小值，找到这个位置后，取出它左边和右边相邻的元素，然后进行比较

  • 如果左边和右边的元素都大于它，那么这个位置就是一个合法的答案。
  • 如果左边小于它，那么在左边的区域肯定可以找到一个合法的答案。
    • 这里可以描述一下，就是中间一列的最小值，然后左边的元素小于它，那么就可以顺着左侧元素开始找，不管如何找，不会穿过中间这一列到右边，所以左侧一定可以找到一个答案，那同理，右侧也是一样的。
  • 如果右边小于它，那么在右边的区域肯定也可以找到一个合法的答案。

假设这里左侧元素小，那么将左侧的二分之n列再进行二分，重复上面的操作，又可以将二分之n列分为二分之一，最后找到一列，在这一列上找到最小的值就是合法的极小值。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// 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};
    }
};