[LeetCode] 每日一题 August 1~10

  • 1 - 1337. 矩阵中战斗力最弱的 K 行；
  • August 1 - 1337. 矩阵中战斗力最弱的K行；
  • August 2 -
  • August 3 -
  • August 4 -
  • August 5 -
  • August 6 -
  • August 7 -
  • August 8 -
  • August 9 -
  • August 10 -

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

描述

给你一个大小为 m * n 的矩阵 mat，矩阵由若干军人和平民组成，分别用 1 和 0 表示。

请你返回矩阵中战斗力最弱的 k 行的索引，按从最弱到最强排序。

如果第 i 行的军人数量少于第 j 行，或者两行军人数量相同但 i 小于 j，那么我们认为第 i 行的战斗力比第 j 行弱。

军人 总是 排在一行中的靠前位置，也就是说 1 总是出现在 0 之前。

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
输入：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 = 3
输出：[2,0,3]
解释：
每行中的军人数目：
行 0 -> 2 
行 1 -> 4 
行 2 -> 1 
行 3 -> 2 
行 4 -> 5 
从最弱到最强对这些行排序后得到 [2,0,3,1,4]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入：mat = 
[[1,0,0,0],
 [1,1,1,1],
 [1,0,0,0],
 [1,0,0,0]], 
k = 2
输出：[0,2]
解释： 
每行中的军人数目：
行 0 -> 1 
行 1 -> 4 
行 2 -> 1 
行 3 -> 1 
从最弱到最强对这些行排序后得到 [0,2,3,1]

思路

第一个能想到的解题思路是，先统计每一行 1 的个数，然后将结果进行排序，按照 1 的个数从小到大排序，如果 1 的个数相同，再按照行号从小到大排序。排好序的数组取出前 K 位即为答案。

此题还有第二种解法。在第一种解法中，并没有用到题目中“军人 总是 排在一行中的靠前位置，也就是说 1 总是出现在 0 之前。”这一条件。由于有了这个条件，使得如果按照列去遍历，最先出现 0 的行，则是最弱的行。行号小的先被遍历到，所以相同数量 1 的行，行号小的会排在前面。最后记得再添加上全 1 的行。同样，最终输出取出前 K 位即为答案。此题解法二才是最优雅最高效的解法。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
        vector<int>temp;
        vector<int>result;
        for(int j=0; j<mat[0].size(); j++){
            for(int i=0; i<mat.size(); i++){
                if(mat[i][j]==0 && (j==0||mat[i][j-1]!=0)){
                    temp.push_back(i);
                }
            }
        }
        for(int i=0; i<mat.size(); i++){
            if(mat[i][mat[0].size()-1]==1){
                temp.push_back(i);
            }
        }
        for(int j=0; j<k; j++){
            result.push_back(temp[j]);
        }
        return result;
    }
};