c – 搜索mn的二维数组中的元素,即行和列

概述您将获得一个MxN的2D数组,该数组按行和列顺序排序.搜索元素的有效方法是什么？ 从矩阵的右上角位置v开始.如果它是您正在寻找的项目x,那么您已经完成了.如果v小于您要查找的项目,请向下移动.如果v大于您要查找的项目,请向左移动.重复,直到你到达矩阵的末端. 正确性证明： 如果右上角的项目等于x,则无需证明.考虑两个案例 v < x 在这种情况下,我们知道顶行中的所有元素都小于x.因此,我们可以忽 您将获得一个MxN的2D数组,该数组按行和列顺序排序.搜索元素的有效方法是什么？解决方法 从矩阵的右上角位置v开始.如果它是您正在寻找的项目x,那么您已经完成了.如果v小于您要查找的项目,请向下移动.如果v大于您要查找的项目,请向左移动.重复,直到你到达矩阵的末端.

正确性证明：

如果右上角的项目等于x,则无需证明.考虑两个案例

v < x

在这种情况下,我们知道顶行中的所有元素都小于x.因此,我们可以忽略整个顶行并向下移动.

因此,我们可以去

1 2 3 4 5 61 * * * * * v2 * * * * * *3 * * * * * * 4 * * * * * *5 * * * * * *

至

1 2 3 4 5 61 . . . . . .2 * * * * * v3 * * * * * * 4 * * * * * *5 * * * * * *

也就是说,我们最终遇到了一个小问题.

另一种情况是

v > x

在这种情况下,我们知道右列中的所有元素都大于x.因此,我们可以忽略整个右列并向左移动.

1 2 3 4 5 61 * * * * * v2 * * * * * *3 * * * * * * 4 * * * * * *5 * * * * * *

至

1 2 3 4 5 61 * * * * v .2 * * * * * .3 * * * * * .4 * * * * * .5 * * * * * .

同样,我们最终遇到了一个小问题.通过归纳,我们完成了.该算法具有时间复杂度O(m n).

编辑：

Ted Hopp链接到这个想法的绝对美丽的扩展,提供更好的性能.

这是个主意.在我上面给出的算法中,我们的想法是我们可以一次性排除整个行或列.他链接的想法是在时间上消除整个象限.这个想法很简单

* * * * * ** * * * * ** * * * * * <- binary search* * * * * ** * * * * *

二进制搜索中间行.这将为您提供项目,或包含您正在寻找的项目的位置

* * * * * ** * * * * ** * * a|b * <- x between a,b* * * * * ** * * * * *

现在,这是关键的见解.可以立即排除整个左上象限和整个右下象限;左上角的所有元素都小于a,右下角的所有元素都大于b.

. . . . * *. . . . * *. . . a|b .* * * * . .* * * * . .

现在递归剩下的两件作品.此外,您可以在中间行或左上角到右下角度执行相同的 *** 作,具体取决于哪个将产生最大增益.

总结

以上是内存溢出为你收集整理的c – 搜索m / n的二维数组中的元素,即行和列全部内容，希望文章能够帮你解决c – 搜索m / n的二维数组中的元素,即行和列所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。