Title source

• leetcode：378. In order matrix K Small elements

Title Description

class Solution {
    
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
    

    }
};

title

Analyze the data

（1） Data volume . It can be seen from the following ：

• This is a square .
• Maximum amount of data ： $300\ast 300=6\ast 10^4$
  • Algorithm complexity cannot be $O(N^2)$, Because it will surpass $10^8$
  • At least it should be $O(N\ast logN)$
    

（2） Data features

• The value range is relatively large , So fill in the form pass
• Increasing from left to right , Increase from top to bottom ,
  • That is, they are monotonous , therefore , reflection ： How to use it ？ Can we dichotomy or use this feature to eliminate some data ？
  • in addition ,matrix[0][0] Is the minimum ,matrix[n-1][n-1] Is the maximum value. .
• from k The value range of k You can find any number in the matrix

Two points （ Optimal solution ）

Ideas

• The smallest number in the whole matrix is the number in the upper left corner ( Assuming that 1), The largest number is the number in the lower right corner ( Assuming that 1000).
• The first k Small number ( hypothesis k=100) It must be [1, 1000] Between .
• How to find this k Small numbers ？
  • Look for the <= 500 There are a few of them ？ If there is 200 individual , Then the goal is big , therefore
  • Look again <= 250 There are a few of them ？ If there is 50 individual , Then the goal is small , therefore
  • Look again <=375 There are a few of them ？ If there is 100 individual , But there is not necessarily this number in the array , So it should be <=375（>375 The number of will be eliminated ） And the number closest to it
• therefore , Every two points should return two messages ：
  • <= How many values are there ？
  • Who is closest to it ？

problem

Ideas ： It is required to be less than or equal to target Of

• Try to eliminate the ratio target Big （ Column ）
• Try to keep less than or equal to target Of （ That's ok ）

From here we can find a property ,

• Take any number x Satisfy $l<=x<=r$, Then the matrix is not greater than midx Number of numbers , It must all be distributed in the upper left corner of the matrix .
• Such as below , take x=8：

problem

Code

Complexity ： O((N + M) * log(max - min))

Merge sort ( Use heap )

Ideas

In the whole matrix , Pop up the smallest value in the matrix every time , The first k What is popped out is the data we want

that , The smallest value in the pop-up matrix every time ？

When we see the following ordered matrix , We know that the number in the upper left corner is the smallest of the whole matrix .

But after popping it , How can we ensure that the smallest value in the whole matrix can be found every time next ？

The key to solving this problem , Is to maintain a group “ Minimum candidate ”.

What needs to be ensured is that the minimum value must be generated from this group of candidates , So just pop up the smallest one from the candidates every time .

Let's choose the first group of candidates , Here you can select the first column , Because every number is the minimum value of its corresponding line , The global minimum must be in it

The first pop-up is simple , Put the... In the top left corner 1 Pop it up .

1 After pop-up , How can we find the next candidate ？

It's simple , Just move the pop-up position one space to the right , Isn't it possible to ensure that every number in the candidate list is the minimum value of each row , The global minimum must be among them ！

We pop up the minimum number of candidates each time , Then fill in the one on the right of the candidate who popped up last time , It can always ensure that the global minimum value is generated in the candidate list ,

···