在矩阵中搜索值的算法设计

Question

这个问题不是作业，只是出于个人兴趣，主要是我的好奇心。

我的教授在课堂上谈到了这个问题一会儿，但他没有谈太多。下面是问题：

给定一个 mxn 矩阵 A，其整数元素沿水平和垂直方向排序 分别方向。我需要开发一个递归程序来搜索查询值是否为 位于 A 中。讨论您的设计的时间复杂度。

所以我想了一会儿这个问题。我的第一种方法是检查基本情况：第一个元素和最后一个元素

检查第一个元素是否> >项目检查最后一个元素是否< item

item 是我想要找到的

这是虚数矩阵：（ x 可以是任何数字，但是这个矩阵是垂直和水平排序的）

             first     x          x        x         x
                 x     x          x        x         x
                 x     x         mid       x         x
                 x     x          x        x         x
                 x     x          x        x         last

在我检查基本情况并确保我想要找到的“item”在里面之后这个矩阵的范围，我不知道是否可以从矩阵中的“中间”检查（如二分搜索）。如果项目<中，然后关注左半部分。如果项目>中，然后关注右半部分。

但是，然后我尝试制作一个如下所示的矩阵，我的“项目”是 10

                 1     2          3        4         5
                 2     4          7        8          9
                 3     6          10       11         12

如果我按照我之前所说的方式操作：由于 10 比中间的“7”大，所以我专注于右侧部分。然后我检查“8”，因为10比“8”大，所以我搜索正确的部分。但 10 不正确......

任何人都可以给我想法或见解如何解决这个问题吗？多谢

Answer 1

从左下角开始（在您的示例中包含 3 的那个）。

1. 如果当前值小于您要搜索的值，则向右走。
2. 如果当前值大于您要搜索的值，则向上。
3. 如果当前值等于您要搜索的值，则返回 true。
4. 如果您超出了矩阵，则返回false。

这是 O(n + m)，其中 n 和 m 是矩阵中的行数和列数。这是因为在每一步中，您都完全排除了整行或整列。

Answer 2

时间上的最佳解决方案是O(1)，并且是使用哈希表来跟踪矩阵中的哪些元素。如果空间有问题，也可以使用布隆过滤器。

然而，由于它们已分类，因此可能不值得添加所有机器。

我认为问题正在寻找的解决方案是一个 O(N) 解决方案（其中矩阵的大小为 NxN）；从左上角到左下角再到右下角，直到找到大于查询的元素。然后，您通过向右上角蠕动来搜索“水平曲线”，每次执行比较以查看是否超出或低于查询（向右或向上，具体取决于）。

您可以考虑的另一种方法是跟踪窗口 lower_c lower_c查询<每列 c 的 higher_c，从左到右。该窗口的大小始终为 2。