第31087题 单选题
已知m行n列的有序矩阵满足每行从左到右升序、每列从上到下升序,要统计矩阵中小于等于目标值target的元素总数,下列关于最优实现方案的说法正确的是?

本题默认讨论通用有序矩阵场景,不考虑元素全相等、矩阵退化为向量等特殊边界场景。

A

仅能逐行逐列遍历所有元素统计,时间复杂度为O(mn),不存在更优方案

B

对每行执行二分查找统计符合条件的元素个数,时间复杂度为O(m log n),这是通用场景下的最优方案

C

从矩阵右上角出发遍历,当前元素小于等于target时累加当前行对应数量后向下移动,否则向左移动,时间复杂度为O(m+n),是通用场景下的最优方案

D

从矩阵左上角出发遍历,当前元素小于等于target时累加计数后向右或向下移动,时间复杂度为O(m+n),是通用场景下的最优方案

程序运行统计
暂无判题统计
提交0次 正确率0.00%
答案解析