第31085题 单选题
在每行从左到右升序、每列从上到下升序的n×n有序矩阵中,统计小于等于目标值k的元素总数,以下哪种实现方法时间复杂度最优且逻辑正确?

矩阵所有元素均为整数,n≥1,要求不使用暴力遍历所有元素的思路。

A

从矩阵右上角开始遍历,若当前元素≤k,则当前行该元素左侧所有元素均满足条件,累加当前行剩余元素数量后向下移动一行;若当前元素>k,则向左移动一列,时间复杂度为O(n)

B

对每一行单独使用二分查找定位第一个大于k的元素下标,累加所有行的下标值得到总数,时间复杂度为O(nlogn)

C

从矩阵左上角开始遍历,若当前元素>k则直接跳转至下一行遍历,时间复杂度为O(n)

D

将矩阵所有元素取出后排序,再统计小于等于k的元素个数,时间复杂度为O(n²logn)

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