Leetcode-378. The k-th smallest element in ordered matrix

yew0 2020-11-09 22:18:15
leetcode-378. leetcode k-th th smallest

The title is shown in the figure below ： The main idea of the title is to give a n*n Matrix , Each row from left to right and each column from top to bottom is an incremental sequence , Find the number... In the matrix k Small number .

Scheme 1 ：

The simplest way is to put all the numbers in the matrix in a sequence , Reorder from small to large , And then output number k Number , Violence solution .

Implementation code ：

class Solution {
public:
int kthSmallest1(vector<vector<int>>& matrix, int k) {
int m;
int nNum = 0;
for(int i=0; i<matrix.size(); i++) {
for(int j=0; j<matrix[i].size(); j++) {
m[nNum++] = matrix[i][j];
}
}
sort(m, m+nNum);
return m[k-1];
}
};

Option two ：

Because every row and every column of the matrix is ordered , You can use binary search to do ; Take the average of the two values in the matrix to find , The average is compared to the number in the matrix , From top to bottom , From right to left , If the average value is greater than or equal to the th N It's worth. So , That line has N The number is less than the average , The next line starts at N The number starts to compare , Because of the first line N+1 The number is larger than the average , The next line must be larger than the average , So you can start with N The number begins ; Then we get the number that the average value is greater than or equal to the number in the matrix S, If S Greater than or equal to K, The number on the far right R= Average , otherwise , The number on the far left L= Average +1; Look for S The number of , And then K Compare , until R No longer greater than L, Output L.

The following is a diagram of part of the process ：

Example ：[[1,3,5],[2,3,6],[4,5,7]], Find the first K=4 A small number

L： The number on the far left

R： The number on the far right

M：L and R Average value

S： Less than in a matrix M The number of

X： The rightmost position of the current line

Y： Current line position Figure 1 ： Initialization data ,L=1,R=7, To calculate the M=4     Pictures 2 to 6 ： Average it M Compared with the numerical value of the matrix , Figure 2 matrix[Y][X]=5 Than M=4 Big ,X=X-1, Compare the value of the previous digit ; Figure 3 matrix[Y][X]=3 Than M=4 Small , be S Add the number 0 Number of rows ,Y=Y+1, Compare the next line ; Figure 4 matrix[Y][X]=3 Than M=4 Small , be S Add the number 1 Number of rows ,Y=Y+1, Compare the next line ; Figure 5 matrix[Y][X]=5 Than M=4 Big ,X=X-1, Compare the value of the previous digit ; Figure 6 matrix[Y][X]=4 And M=4 equal , be S Add the number 1 Number of rows ; Complete the matrix comparison , To get the final S. Figure 7 ：S=5 Than K=4 Big , therefore R=M=4 Figure 8 ： To calculate the M=2, For the next round of comparison , The comparison process is consistent with that in figures 2 and 6 , until L Greater than or equal to R.

Implementation code ：

class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
int n = matrix.size();
int nm = n - 1;
int nLeft = matrix;
int nRight = matrix[nm][nm];
while(nLeft < nRight) {
int nMid = (nLeft + nRight) / 2.0;
int nMaxx = 0;
int nMaxy = nm;
int nSize = 0;
while(nMaxy >= 0 && nMaxx < n) {
if(matrix[nMaxx][nMaxy] <= nMid) {
nSize += (nMaxy + 1);
nMaxx++;
}
else {
nMaxy--;
}
}
if(nSize >= k) {
nRight = nMid;
}
else {
nLeft = nMid + 1;
}
}
return nLeft;
}
};

There is a problem to be explained in the above steps ： Why? S Greater than or equal to K When R No M-1, It is R=M？

Because when S==K When , There may be M Is equal to a certain value in the matrix , Join in M-1 It will lead to wrong answers . step 1 To calculate the S be equal to 2, It's just following K equal ,M The value of is exactly equal to that in the array , If M-1 Words R Is equal to 2, And the end result is 2. If there are multiple identical values in a matrix ,S It may be greater than K,M Equal to the number required , There will also be the final wrong answer .L Can add 1 The reason is that ,L Of S The number ratio is K Less , therefore +1 It's possible to become S==K, until L==R. Love can pay more attention to the official account to see more articles