leetcode1337. Row K with the weakest combat effectiveness in the matrix

LeetCode Series articles

One 、 Title Description

   Give you a size of $m\times 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 are always at the top of the line , in other words $1$ Always in $0$ Before .

Two 、 Example

   Input ： mat = [ [1, 1, 0, 0, 0 ],
          [1, 1, 1, 1, 0 ],
          [1, 0, 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]

3、 ... and 、 Main idea

   Want to find out the weakest battle effectiveness in the matrix K That's ok , We can sort each row in the matrix according to the strength of combat effectiveness , Then you can select the one with the weakest combat effectiveness K That's ok .
 
   In the process of sorting, you need to compare the combat effectiveness of each row , So we need to set up a way to compare combat effectiveness .

• According to the meaning of the question , When comparing combat effectiveness , You need to compare the two lines first 1 The number of .
• If in two lines 1 The number of different , be 1 The battle effectiveness of the row with a small number of is weak .
• If in two lines 1 The same number of , You need to continue to compare line numbers , The line with smaller line size has weaker combat effectiveness .

 
After sorting each row by combat effectiveness according to this comparison method , We can select the one with the weakest combat effectiveness K That's ok .

Four 、 Code implementation

When implementing code , It can be used pair To show the combat effectiveness of a certain line .

• In this line 1 As the number of pair among first member .
• Take the line number of this line as pair In the middle of second member .

 
   because pair Type variables are compared first by default first member , If first Compare the same members second member , This is just a symbol of the rules for comparison of combat effectiveness , The sorting method can be arbitrary , Here, take heap sorting as an example .
 
So the steps to solve the problem are as follows ：

1. Traverse the rows of the matrix , Count the... In each row 1 The number of , constitute <1 The number of , Line number > The key/value pair .
2. Use the combat power of each line to build piles （ Little heap ）.
3. Take out the weakest weapon from the top of the pile k That's ok .

 
The code is as follows ：
Explain ：

• Because... In each line 1 Always in 0 Previous , So in a row of Statistics 1 The binary search method can be used to find the number of , Find the last one in the line 1 The location of pos, here pos+1 The corresponding is in this line 1 The number of .
• When building a reactor , It's best not to put each line of pair Put them in the heap one by one , Instead, you should use these pair Build the reactor , Because the time complexity of the former is $O(NlogN)$, The time complexity of the latter is $O(N)$.