algorithm - 单调递增二维数组

Question

给出一个算法，在行和列单调递增的 n×n 矩阵中找到给定元素 x(给出坐标)。

我的想法:减少问题集大小。

在第 1 列中，找到 <= x 的最大元素。我们知道 x 必须在这一行或之后(下)。在矩阵的最后一列中，找到 >= x 的最小元素。我们知道 x 必须在这一行或之前。对矩阵的第一行和最后一行执行相同的操作。我们现在已经定义了一个子矩阵，如果 x 在矩阵中，它就在这个子矩阵中。现在在这个子矩阵上重复算法......沿着这些线。

[YAAQ:又一个数组问题。]

Answer 1

我认为您不能希望超过 O(N)，这是可以实现的。 (N是矩阵的宽度)。

为什么你不能指望更多

想象一个这样的矩阵:

0 0 0 0 0 0 ... 0 0 x
0 0 0 0 0 0 ... 0 x 2
0 0 0 0 0 0 ... x 2 2
.....................
0 0 0 0 0 x ... 2 2 2
0 0 0 0 x 2 ... 2 2 2
0 0 0 x 2 2 ... 2 2 2
0 0 x 2 2 2 ... 2 2 2
0 x 2 2 2 2 ... 2 2 2
x 2 2 2 2 2 ... 2 2 2

其中 x 是一个未知数(不是同一个数字，即它可能在每一列中都不同)。为了满足矩阵的单调性，您可以在所有的x 位置放置0、1 或2 中的任意一个。因此，要查找矩阵中是否有 1，您必须检查所有 x 位置，并且有 N 个位置。

如何实现 O(n)

假设您必须为所有行找到具有 number > q(给定数字)的第一列索引。你从矩阵的右上角开始；如果你看到的数字更大，你就向左走；否则下去。当你在最后一行时结束。你跌倒的地方就是你寻找的地方。如果他们中的任何一个有您搜索的号码，您就找到了。

此算法是O(n)，因为在每一步中，您要么向左走，要么向下走。总的来说，它不能超过 N 次向左和 N 次向下。因此它是 O(n)。