K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
矩阵所有元素均为整数,n≥1,要求不使用暴力遍历所有元素的思路。
从矩阵右上角开始遍历,若当前元素≤k,则当前行该元素左侧所有元素均满足条件,累加当前行剩余元素数量后向下移动一行;若当前元素>k,则向左移动一列,时间复杂度为O(n)
对每一行单独使用二分查找定位第一个大于k的元素下标,累加所有行的下标值得到总数,时间复杂度为O(nlogn)
从矩阵左上角开始遍历,若当前元素>k则直接跳转至下一行遍历,时间复杂度为O(n)
将矩阵所有元素取出后排序,再统计小于等于k的元素个数,时间复杂度为O(n²logn)