K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
本题要求选择利用矩阵有序特性的最优统计方案,不考虑暴力遍历等低效率实现。
从矩阵右上角出发,若当前元素≤k则累加当前列的所有行数,指针左移,否则指针下移,时间复杂度O(n)
逐行对每行做二分查找,统计每行小于等于k的元素个数后累加,时间复杂度O(nlogn)
从矩阵左上角出发,若当前元素≤k则指针右移,否则指针下移,遍历过程中统计符合条件的元素,时间复杂度O(n)
将矩阵所有元素存入一维数组,排序后统计小于等于k的元素数量,时间复杂度O(n²logn)