【宫水三叶の真题精选】一题双解 : 从 O(m * n) 到 O(m + n) 的优化

朴素解法

一个朴素的做法是，直接对矩阵 进行遍历。

由于题目确保有解，因此当我们找到 时，直接将二元组 作为答案输出即可。

代码：

import java.util.*;

public class Solution {
    public int[] findElement(int[][] mat, int n, int m, int x) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == x) return new int[]{i, j};
            }
        }
        return new int[]{-1, -1}; // never
    }
}

• 时间复杂度：
• 空间复杂度：

抽象 BST

显然在「朴素解法」中，我们没有利用到「矩阵的行和列都是从小到大有序」的特性。

事实上，我们可以将二维矩阵抽象成「以右上角为根的 BST」：

那么我们可以从根（右上角）开始搜索，如果当前的节点不等于目标值，可以按照树的搜索顺序进行：

1. 当前节点「大于」目标值，搜索当前节点的「左子树」，也就是当前矩阵位置的「左方格子」，即 j--
2. 当前节点「小于」目标值，搜索当前节点的「右子树」，也就是当前矩阵位置的「下方格子」，即 i++

代码：

import java.util.*;

public class Solution {
    public int[] findElement(int[][] mat, int n, int m, int x) {
        // 从右上角开始搜索
        int i = 0, j = m - 1;
        while (check(i, j, n, m) && mat[i][j] != x) {
            if (mat[i][j] > x) {
                j--;
            } else {
                i++;
            }
        }
        return new int[]{i, j};
    }
    boolean check(int i, int j, int n, int m) {
        return i >= 0 && i < n && j >= 0 && j < m;
    }
}

• 时间复杂度：
• 空间复杂度：

最后

这是我们「必考真题 の 精选」系列文章的第 No.86 篇，系列开始于 2021/07/01。

该系列会将牛客网中「题霸 - 面试必考真题」中比较经典而又不过时的题目都讲一遍。

在提供追求「证明」&「思路」的同时，提供最为简洁的代码。

欢迎关注，交个朋友 (｀・ω・´)