目录

lc1337.矩阵中战斗力最弱的K行

Shen 收录于每日一题

2021-07-29 约 282 字预计阅读 1 分钟

目录

1337. 矩阵中战斗力最弱的 K 行

二分查找+topK

1总是排在前面，所以我们只需要通过二分查找找到最后一个1的位置。
再利用最小堆找出topK小的数
T:O(mlogn+klogm)
- O(mlogn):二分查找
- O(m):构建优先队列，参考：https://www.zhihu.com/question/20729324
- O(klogm):topK

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


typedef pair<int, int> PII;
class Solution {
public:
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
        // O(mlogn):二分查找
        vector<PII> cmp;
        for(int i = 0; i < mat.size(); i++){
            int l = -1, r = mat[i].size() - 1;
            while(l < r){
                int mid = (l + r + 1) >> 1;
                if(mat[i][mid] == 1){
                    l = mid;
                }else{
                    r = mid - 1;
                }
            }

            cmp.push_back({l, i});
        }
        // O(m):构建优先队列
        priority_queue<PII, vector<PII>, greater<PII>> q(cmp.begin(), cmp.end());
        vector<int> ans;
        // O(klogm):topK
        for (int i = 0; i < k; ++i) {
            ans.push_back(q.top().second);
            q.pop();
        }
        return ans;
    }
};