算法

(排序) $O(nlogn)$

先统计一下每行中$1$的个数，记做$cnt[i]$，然后对二元组$(i, cnt[i])$按要求排序，最后把前$k$个计入答案就行了。

C++ 代码

class Solution {
public:
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
        int n = mat.size();
        int m = mat[0].size();
        vector<int> cnt(n, 0);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (mat[i][j]) cnt[i]++;
            }
        }
        vector<pair<int, int>> vecs;
        for (int i = 0; i < n; ++i) {
            vecs.push_back(make_pair(i, cnt[i]));
        }
        sort(vecs.begin(), vecs.end(), [&](pair<int, int> a, pair<int, int> b) {
            return a.second < b.second || (a.first < b.first && a.second == b.second);
        });
        vector<int> res;
        for (auto it : vecs) {
            if (k) {
                res.push_back(it.first);
                k--;
            }
        }
        return res;
    }
};