Leetcode 1337. Row K with the weakest combat effectiveness in the matrix

1337、 The weakest in the matrix K That's ok

1） Title Description

Give you a size of m * n Matrix mat, The matrix consists of a number of soldiers and civilians , Use them separately 1 and 0 Express .

Please return to the weakest in the matrix k Index of rows , Sort by weakest to strongest .

If the first i The number of soldiers in line is less than the number of j That's ok , Or two lines of soldiers in the same number but i Less than j, So we think the i The battle effectiveness of the line is better than the first j Row weakness .

Soldiers Always The front position in a row , in other words 1 Always in 0 Before .

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 = 3
 Output ：[2,0,3]
 explain ：
 The number of soldiers in each line ：
 That's ok  0 -> 2 
 That's ok  1 -> 4 
 That's ok  2 -> 1 
 That's ok  3 -> 2 
 That's ok  4 -> 5 
 Sort these rows from the weakest to the strongest to get  [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 = 2
 Output ：[0,2]
 explain ： 
 The number of soldiers in each line ：
 That's ok  0 -> 1 
 That's ok  1 -> 4 
 That's ok  2 -> 1 
 That's ok  3 -> 1 
 Sort these rows from the weakest to the strongest to get  [0,2,3,1]

Tips ：

• m == mat.length
• n == mat[i].length
• 2 <= n, m <= 100
• 1 <= k <= m
• matrix[i][j] No 0 Namely 1

2） analysis

• Find the last... In each line by bisection 1 The subscript , To calculate the combat effectiveness of each line , Gain combat effectiveness array ;
• Assign the combat effectiveness of each row to the temporary array , And sort it out ;
• Through violent comparison , Find the first... Of the temporary array k The subscript of a value in the combat effectiveness array .

3）C++ Code

class Solution {
    
public:
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
    
        vector<int> res;
        for(int i=0;i<mat.size();i++){
    
            int left=0;
            int right=mat[0].size()-1;
            while(left<=right){
    
                int mid=(left+right)/2;
                if(!mat[i][mid])
                    right=mid-1;
                else
                    left=mid+1;
            }
            res.push_back(left+1);
        }
        vector<int>temp=res;
        sort(temp.begin(),temp.end());
        vector<int> ans;
        for(int i=0;i<k;i++){
    
            for(int j=0;j<res.size();j++){
    
                if(res[j]==temp[i]){
    
                    ans.push_back(j);
                    res[j]=INT_MAX;
                    break;
                }
            }
        }
        return ans;
    }
};