第2.3篇·矩阵排序查找

算法是求职的敲门砖，大厂面试一面几乎都会问算法题，以此来考察候选人的思维逻辑及编码能力。

今天要AC的题目叫做「排序矩阵查找」，在 leetcode 上的原题链接为：https://leetcode.cn/problems/sorted-matrix-search-lcci/

1. 题目

给定M×N矩阵，每一行、每一列都按升序排列，请编写代码找出某元素。

示例:

现有矩阵 matrix 如下：

[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]

给定 target = 5，返回 true。

给定 target = 20，返回 false。

2. 解题思路

题目非常容易理解：给定一个二维数组以及一个 target 值，判断该值是否在二维数组中存在。

作为一个冷酷无情的 JDK API 选手，第一时间我就想到了 Set 这个数据结构（当然 List 也可以，就是会消耗比 Set 更大的内存），Set 是一个不可重复的容器，只要对二维数组（矩阵）进行遍历，将所有元素都放到 Set 中，最后再调用 contains 方法来判断 target 是否存在于 Set 容器中即可得到答案。

用 Java 实现上述思路的代码是：

上述示例代码在 leetcode 上的执行结果是：

上面这种解法算是一种偷懒的做法，借助了 JDK 提供的工具类进行解答。类似的做法还有很多：比如将 Set 换成 List、String 等等。

除此之外，我们如果只用原生类型尝试解题，就可以使用迭代法进行解答，即对该二维数组进行遍历，只要找到了该元素就返回 true，否则就返回 false。

用 Java 实现上述思路的代码是：

上述示例代码在 leetcode 上的执行结果是：

上述第二种迭代的解法虽然非常简单，但是有很多无意义的迭代，有很大可以优化的空间，要知道，该矩阵有一个很重要的特性：每一行、每一列都按升序排列。

我们可以基于这个特性对迭代法进行优化，从而达到少迭代的目的，减少耗时。

还是从第一行开始遍历，如果 targte 大于这一行的最大值（即最后一列），那么直接修改遍历的行号进行下一行遍历。否则，就修改遍历的列号进行本行内列的遍历，直到找到相同的值或遍历完本行。

用 Java 实现上述思路的代码是：

上述示例代码在 leetcode 上的执行结果是：

可以看到，执行用时为5ms，而第二种解法的用时是10ms，减少了一半，效果显著。

最后，本文收录于个人语雀知识库: 我所理解的后端技术，欢迎来访。