Update Readme.md

wisdompeak · web-flow · commit 137fde564614 · 2021-06-14T17:11:22.000-07:00
diff --git a/Heap/1439.Find-the-Kth-Smallest-Sum-of-a-Matrix-With-Sorted-Rows/Readme.md b/Heap/1439.Find-the-Kth-Smallest-Sum-of-a-Matrix-With-Sorted-Rows/Readme.md
@@ -7,7 +7,7 @@
 
 &#36880;&#34892;&#25512;&#36827;&#65292;&#22788;&#29702;&#23436;&#26368;&#21518;&#19968;&#34892;&#20043;&#21518;&#65292;presum&#23601;&#21253;&#21547;&#20102;&#21069;k&#20010;sum&#12290;
 
-#### &#26041;&#27861;2&#65306;Merge N sorted List.
-&#25105;&#20204;&#30340;&#21021;&#22987;&#29366;&#24577;&#26159;sum&#26368;&#23567;&#30340;array&#65292;&#20063;&#23601;&#26159;&#27599;&#34892;&#21462;&#31532;&#19968;&#20010;&#20803;&#32032;&#12290;&#28982;&#21518;&#22522;&#20110;&#36825;&#20010;array&#65292;&#20998;&#21035;&#23558;&#27599;&#34892;&#30340;&#20803;&#32032;&#26367;&#25442;&#20026;&#35813;&#34892;&#30340;&#19979;&#19968;&#20010;&#65292;&#36825;&#26679;&#23601;&#21487;&#20197;&#25193;&#23637;&#20986;m&#20010;array...&#23558;&#25152;&#26377;&#25299;&#23637;&#20986;&#30340;array&#25918;&#22312;&#19968;&#20010;PQ&#37324;&#65292;&#28982;&#21518;&#27599;&#27425;&#24377;&#20986;&#30340;&#26159;sum&#26368;&#23567;&#30340;array&#65292;&#32487;&#32493;&#25299;&#23637;...&#21487;&#35265;&#65292;&#27492;&#39064;&#26412;&#36136;&#19978;&#26159;&#23601;N sorted list&#30340;&#24402;&#24182;&#25490;&#24207;&#12290;
+#### &#26041;&#27861;2&#65306;PQ
+&#25105;&#20204;&#20174;&#23567;&#21040;&#22823;&#25628;&#32034;sum&#12290;&#21021;&#22987;&#29366;&#24577;&#65288;&#21363;&#26368;&#23567;&#30340;sum&#65289;&#24517;&#28982;&#23545;&#24212;&#30528;&#27599;&#34892;&#21462;&#31532;&#19968;&#20010;&#20803;&#32032;&#12290;&#28982;&#21518;&#22522;&#20110;&#36825;&#20010;idx array&#65292;&#21487;&#20197;&#25193;&#23637;&#20986;m&#20010;idx array&#65292;&#21363;&#23558;&#27599;&#34892;&#30340;&#25351;&#38024;&#31227;&#21521;&#35813;&#34892;&#30340;&#19979;&#19968;&#20010;&#65292;...&#23558;&#25152;&#26377;&#25299;&#23637;&#20986;&#30340;array sum&#25918;&#22312;&#19968;&#20010;PQ&#37324;&#65292;&#24377;&#20986;&#24403;&#21069;&#26368;&#23567;&#30340;array sum&#32487;&#32493;&#25299;&#23637;... &#21487;&#35265;&#65292;&#27492;&#39064;&#26412;&#36136;&#19978;&#26159;&#23601;N sorted list&#30340;&#24402;&#24182;&#25490;&#24207;&#12290;
 
-&#27880;&#24847;&#30340;&#26159;&#65292;&#25105;&#20204;&#22312;&#26412;&#39064;&#37319;&#29992;&#30340;&#25968;&#25454;&#32467;&#26500;&#26159;set&#32780;&#19981;&#26159;PQ&#65292;&#26159;&#22240;&#20026;&#32771;&#34385;&#21040;&#21435;&#37325;&#30340;&#38382;&#39064;&#12290;&#35201;&#35686;&#24789;&#26576;&#31181;array&#30340;&#32452;&#21512;&#65292;&#21487;&#33021;&#20250;&#30001;&#19981;&#21516;&#30340;array&#25299;&#23637;&#32780;&#26469;&#65292;&#25105;&#20204;&#19981;&#33021;&#37325;&#22797;&#21152;&#20837;&#36827;PQ&#65292;&#24517;&#39035;&#20570;visited&#26631;&#35760;&#12290;&#22914;&#26524;&#29992;&#26377;&#24207;&#30340;set&#21487;&#20197;&#21516;&#26102;&#36215;&#21040;&#21435;&#37325;&#30340;&#20316;&#29992;&#65292;&#19968;&#20030;&#20004;&#24471;&#12290;
+&#27880;&#24847;&#30340;&#26159;&#65292;idx array&#21487;&#33021;&#20250;&#26377;&#37325;&#22797;&#65292;&#38656;&#35201;&#29992;&#19968;&#20010;&#38598;&#21512;&#26469;&#21435;&#37325;&#12290;&#27604;&#22914;[[1,2],[1,2]]&#65292;&#21021;&#22987;&#29366;&#24577;&#26159;{2, {0,0}}&#65307;&#31532;&#20108;&#36718;&#20250;&#21152;&#20837;{3, {1,0}},{3, {0,1}}&#65307;&#22312;&#31532;&#19977;&#36718;&#65292;&#31532;&#20108;&#36718;&#30340;&#21069;&#32773;&#20250;&#23548;&#20837;{4, {1,1}}&#65292;&#21518;&#32773;&#20063;&#20250;&#23548;&#20837;{4,{1,1}}&#65292;&#36825;&#26679;&#23601;&#20250;&#23558;{1,1}&#36825;&#20010;&#32452;&#21512;&#37325;&#22797;&#35745;&#25968;&#20004;&#27425;&#12290;

-Original file line number
+Diff line change
 逐行推进，处理完最后一行之后，presum就包含了前k个sum。
 -#### 方法2：Merge N sorted List.
 -我们的初始状态是sum最小的array，也就是每行取第一个元素。然后基于这个array，分别将每行的元素替换为该行的下一个，这样就可以扩展出m个array...将所有拓展出的array放在一个PQ里，然后每次弹出的是sum最小的array，继续拓展...可见，此题本质上是就N sorted list的归并排序。
 +#### 方法2：PQ
 +我们从小到大搜索sum。初始状态（即最小的sum）必然对应着每行取第一个元素。然后基于这个idx array，可以扩展出m个idx array，即将每行的指针移向该行的下一个，...将所有拓展出的array sum放在一个PQ里，弹出当前最小的array sum继续拓展... 可见，此题本质上是就N sorted list的归并排序。
 -注意的是，我们在本题采用的数据结构是set而不是PQ，是因为考虑到去重的问题。要警惕某种array的组合，可能会由不同的array拓展而来，我们不能重复加入进PQ，必须做visited标记。如果用有序的set可以同时起到去重的作用，一举两得。
 +注意的是，idx array可能会有重复，需要用一个集合来去重。比如[[1,2],[1,2]]，初始状态是{2, {0,0}}；第二轮会加入{3, {1,0}},{3, {0,1}}；在第三轮，第二轮的前者会导入{4, {1,1}}，后者也会导入{4,{1,1}}，这样就会将{1,1}这个组合重复计数两次。