LeetCode-1341. The K Weakest Rows in a Matrix

LeetCode-1341. The K Weakest Rows in a Matrix

Given a ​​m * n​​​ matrix ​​mat​​ of ones (representing soldiers) and zeros (representing civilians), return the indexes of the ​​k​​ weakest rows in the matrix ordered from the weakest to the strongest.

A row i is weaker than row j, if the number of soldiers in row i is less than the number of soldiers in row j, or they have the same number of soldiers but i is less than j. Soldiers are always stand in the frontier of a row, that is, always ones may appear first and then zeros.

Example 1:

Input: mat = [[1,1,0,0,0], [1,1,1,1,0], [1,0,0,0,0], [1,1,0,0,0], [1,1,1,1,1]], k = 3Output: [2,0,3]Explanation: The number of soldiers for each row is: row 0 -> 2 row 1 -> 4 row 2 -> 1 row 3 -> 2 row 4 -> 5 Rows ordered from the weakest to the strongest are [2,0,3,1,4]

Example 2:

Input: mat = [[1,0,0,0], [1,1,1,1], [1,0,0,0], [1,0,0,0]], k = 2Output: [0,2]Explanation: The number of soldiers for each row is: row 0 -> 1 row 1 -> 4 row 2 -> 1 row 3 -> 1 Rows ordered from the weakest to the strongest are [0,2,3,1]

Constraints:

​​m == mat.length​​​​n == mat[i].length​​​​2 <= n, m <= 100​​​​1 <= k <= m​​​​matrix[i][j]​​ is either 0or1.

题解：

class Solution {public: static bool cmp(pair a, pair b) { if (a.second != b.second) { return a.second < b.second; } return a.first < b.first; } vector kWeakestRows(vector>& mat, int k) { int m = mat.size(), n = mat[0].size(); vector> num; for (int i = 0; i < m; i++) { int cnt = 0; for (int j = 0; j < n; j++) { if (mat[i][j] == 1) { cnt++; } } num.push_back({i, cnt}); } sort(num.begin(), num.end(), cmp); vector res; for (int i = 0; i < k; i++) { res.push_back(num[i].first); } return res; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。