单调增加2-d阵列

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是未知数字(不是相同的数字,即每列中可能是不同的数字).为了满足矩阵的单调性,您可以在所有位置放置0,1或2中的任何一个x.因此,要查找矩阵中是否有1,您必须检查所有x位置,并且有N个.

如何制作它 O(n)

想象一下,您必须number > q为所有行找到带有(给定数字)的第一列标记.你从矩阵的右上角开始; 如果你看到的数字更大,你就走了; 否则就下去了.当你在最后一行时结束.你去的地方是你搜索的地方.如果他们中的任何一个有你搜索的号码,你就找到了它.

这个算法是O(n)因为在每个步骤中,你要么向左或向下.总的来说,它不会超过N剩余N时间和时间.因此,它O(n).