c – 搜索m / n的二维数组中的元素,即行和列
发布时间:2020-12-16 09:46:46 所属栏目:百科 来源:网络整理
导读:您将获得一个MxN的2D数组,该数组按行和列顺序排序.搜索元素的有效方法是什么? 解决方法 从矩阵的右上角位置v开始.如果它是您正在寻找的项目x,那么您已经完成了.如果v小于您要查找的项目,请向下移动.如果v大于您要查找的项目,请向左移动.重复,直到你到达矩阵
您将获得一个MxN的2D数组,该数组按行和列顺序排序.搜索元素的有效方法是什么?
解决方法
从矩阵的右上角位置v开始.如果它是您正在寻找的项目x,那么您已经完成了.如果v小于您要查找的项目,请向下移动.如果v大于您要查找的项目,请向左移动.重复,直到你到达矩阵的末端.
正确性证明: 如果右上角的项目等于x,则无需证明.考虑两个案例 v < x 在这种情况下,我们知道顶行中的所有元素都小于x.因此,我们可以忽略整个顶行并向下移动. 因此,我们可以去 1 2 3 4 5 6 1 * * * * * v 2 * * * * * * 3 * * * * * * 4 * * * * * * 5 * * * * * * 至 1 2 3 4 5 6 1 . . . . . . 2 * * * * * v 3 * * * * * * 4 * * * * * * 5 * * * * * * 也就是说,我们最终遇到了一个小问题. 另一种情况是 v > x 在这种情况下,我们知道右列中的所有元素都大于x.因此,我们可以忽略整个右列并向左移动. 1 2 3 4 5 6 1 * * * * * v 2 * * * * * * 3 * * * * * * 4 * * * * * * 5 * * * * * * 至 1 2 3 4 5 6 1 * * * * v . 2 * * * * * . 3 * * * * * . 4 * * * * * . 5 * * * * * . 同样,我们最终遇到了一个小问题.通过归纳,我们完成了.该算法具有时间复杂度O(m n). 编辑: Ted Hopp链接到这个想法的绝对美丽的扩展,提供更好的性能. 这是个主意.在我上面给出的算法中,我们的想法是我们可以一次性排除整个行或列.他链接的想法是在时间上消除整个象限.这个想法很简单 * * * * * * * * * * * * * * * * * * <- binary search * * * * * * * * * * * * 二进制搜索中间行.这将为您提供项目,或包含您正在寻找的项目的位置 * * * * * * * * * * * * * * * a|b * <- x between a,b * * * * * * * * * * * * 现在,这是关键的见解.可以立即排除整个左上象限和整个右下象限;左上角的所有元素都小于a,右下角的所有元素都大于b. . . . . * * . . . . * * . . . a|b . * * * * . . * * * * . . 现在递归剩下的两件作品.此外,您可以在中间行或左上角到右下角度执行相同的操作,具体取决于哪个将产生最大增益. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |