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[200001];
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[0][0];
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

 

版权声明
本文为[yew0]所创,转载请带上原文链接,感谢

  1. [front end -- JavaScript] knowledge point (IV) -- memory leakage in the project (I)
  2. This mechanism in JS
  3. Vue 3.0 source code learning 1 --- rendering process of components
  4. Learning the realization of canvas and simple drawing
  5. gin里获取http请求过来的参数
  6. vue3的新特性
  7. Get the parameters from HTTP request in gin
  8. New features of vue3
  9. vue-cli 引入腾讯地图(最新 api,rocketmq原理面试
  10. Vue 学习笔记(3,免费Java高级工程师学习资源
  11. Vue 学习笔记(2,Java编程视频教程
  12. Vue cli introduces Tencent maps (the latest API, rocketmq)
  13. Vue learning notes (3, free Java senior engineer learning resources)
  14. Vue learning notes (2, Java programming video tutorial)
  15. 【Vue】—props属性
  16. 【Vue】—创建组件
  17. [Vue] - props attribute
  18. [Vue] - create component
  19. 浅谈vue响应式原理及发布订阅模式和观察者模式
  20. On Vue responsive principle, publish subscribe mode and observer mode
  21. 浅谈vue响应式原理及发布订阅模式和观察者模式
  22. On Vue responsive principle, publish subscribe mode and observer mode
  23. Xiaobai can understand it. It only takes 4 steps to solve the problem of Vue keep alive cache component
  24. Publish, subscribe and observer of design patterns
  25. Summary of common content added in ES6 + (II)
  26. No.8 Vue element admin learning (III) vuex learning and login method analysis
  27. Write a mini webpack project construction tool
  28. Shopping cart (front-end static page preparation)
  29. Introduction to the fluent platform
  30. Webpack5 cache
  31. The difference between drop-down box select option and datalist
  32. CSS review (III)
  33. Node.js学习笔记【七】
  34. Node.js learning notes [VII]
  35. Vue Router根据后台数据加载不同的组件(思考-&gt;实现-&gt;不止于实现)
  36. Vue router loads different components according to background data (thinking - & gt; Implementation - & gt; (more than implementation)
  37. 【JQuery框架,Java编程教程视频下载
  38. [jQuery framework, Java programming tutorial video download
  39. Vue Router根据后台数据加载不同的组件(思考-&gt;实现-&gt;不止于实现)
  40. Vue router loads different components according to background data (thinking - & gt; Implementation - & gt; (more than implementation)
  41. 【Vue,阿里P8大佬亲自教你
  42. 【Vue基础知识总结 5,字节跳动算法工程师面试经验
  43. [Vue, Ali P8 teaches you personally
  44. [Vue basic knowledge summary 5. Interview experience of byte beating Algorithm Engineer
  45. 【问题记录】- 谷歌浏览器 Html生成PDF
  46. [problem record] - PDF generated by Google browser HTML
  47. 【问题记录】- 谷歌浏览器 Html生成PDF
  48. [problem record] - PDF generated by Google browser HTML
  49. 【JavaScript】查漏补缺 —数组中reduce()方法
  50. [JavaScript] leak checking and defect filling - reduce() method in array
  51. 【重识 HTML (3),350道Java面试真题分享
  52. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  53. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  54. [re recognize HTML (3) and share 350 real Java interview questions
  55. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  56. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  57. 【重识 HTML ,nginx面试题阿里
  58. 【重识 HTML (4),ELK原来这么简单
  59. [re recognize HTML, nginx interview questions]
  60. [re recognize HTML (4). Elk is so simple