KthSmallestElementInASortedMatrix [source code]

public class KthSmallestElementInASortedMatrix {
static
/******************************************************************************/
class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int lo = matrix[0][0], hi = matrix[n - 1][n - 1] + 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            int count = 0, j = n - 1;
            for (int i = 0; i < n; i++) {
                while (j >= 0 && matrix[i][j] > mid)
                    j--;
                count += (j + 1);
            }
            if (count < k)
                lo = mid + 1;
            else
                hi = mid;
        }
        return lo;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        KthSmallestElementInASortedMatrix.Solution tester = new KthSmallestElementInASortedMatrix.Solution();
    }
}

想了半天这个问题还是没有想出什么特别好的办法; 当然这个问题并不是说没有笨办法, 但是这个笨办法对于问题本身的解决并没有什么帮助, 并不能指望这个笨办法的思路能够拓展到更加普遍的一个算法上面; 也就是说这个笨办法本身并不能找到一个能够普遍性适用到这个问题上面的通用思路, intuition; 这种问题就很姜了, 属于一点思路也没有了, 直接拉倒看答案;

按照Binary Search的答案写了一个, 速度是1ms (76%), 是最优解;

2018-04-23 11:30:15 这个题当时居然没有思路吗...哦不对, 这题跟那个k个sorted区间的好像不一样; 这里只是告诉你, row和column都是sorted, 但是并没有告诉你比如[0][C-1]比[1][0]小; 所以直接的两次二分的做法好像不行?

这个题的难度就是是一个对value的二分, 而不是对index的二分(which is the easier kind). 上面最后写的这个做法就是对于每一个尝试性的mid value, 进行一次count, 看看他跟k对比,什么关系; 讲实话这个算法并不是非常的优雅;

另外一个难点就是二叉写法的二分; 一个是注意header以及hi的初始化位置; 另外就是二叉的写法;

j停留的是什么地方? 是第一个<= mid的位置; 所以count最后count的是所有<= mid的个数; 为什么能取这个等号, 很subtle: 因为mid可能是真实存在于这个矩阵里面的; 所以要把等于也算进去;
我们要找的这个最后的结果, kth (1-based) smallest的数字, 最后<=他的, 应该是k个; 这个可以自己在一维数组的例子上面比划一下;
所以如果我们count出来不够k, 说明要找的肯定在右边, 所以向右走; 如果count>k, 向左走, hi=mid因为右端点是exclusive的; 也就是我们要么从lo..hi-1变化到mid+1..hi-1, 要么变化到lo..mid-1, 这个跟三叉写法没有区别;
之前说过, 二叉写法的一个理解方式, 就是可以认为等于的情况是被合并到两边当中的一个里面去了; 这里等于, 也是向左走的; 也就是如果count==k, 也是变化到lo..mid-1. 为什么呢?
这里主要问题是, 当等于的时候, 虽然告诉你count等于k, 看起来好像你得到你需要的结果了, 但是你并不知道mid是不是真实存在于这个矩阵里面, 也就是mid是不是真的对应一个entry; 我们分情况讨论, 不对不用分情况讨论; 因为..算了, 还是分情况讨论;

  • 假如mid真实: 那么我们就应该返回mid, 但是这里的逻辑选择让我们继续走到lo..mid-1, 那么这一层算出来的新mid的leq count肯定不够k, 那么肯定又要往右走; 比如1,2,3,4,5找k等于3, 也就是要翻回3. 首先[1,6),mid=3, k=3, 然后我们向左; [1,3)], mid=2, k=2, 向右; [3,3)], 这个就停了, 这个时候lo停在了3, 是我们想要的; 诶, 为什么; 如果用闭区间理解, 一开始是1..5, 然后1..2, 但是这里算出来的mid就是1, 这个反正还是向右, 变成2..2, mid等于2, 继续向右, 3..2, 停止, 所以这个感觉最后也找到了; 所以跟开闭区间没关系(对mid的计算倒是有点影响), 这个方法就是能成功; 模糊一点的一个理解就是这个情况下, 当你选择了lo..mid-1之后, 肯定会不停失败, 而且是一直是count<k的重新往右回头; 因为count<k更新的是lo, 最后lo会被重新更新回到这个正确并且存在的mid上面来;
  • 假如mid不存在: 那么实际上真正的答案应该是矩阵里面mid的ceiling; 照样, 先无脑扔到左边去, 然后会一直count<k更新lo, 最后停止的时候, lo肯定是重新超过回来了; 所以因为我们要的是ceiling, 才用一个往左扔让他自己往回反弹的思路? 感觉这个理解还是太模糊而且imperative了;

另外一个做法是, 既然等于的情况这么处理, 那么就单独处理: 一个set先把所有的矩阵entry都装起来, 然后等于的时候判断是否存在? 这样其实很差, 因为你初始化这个set就需要N^2了, 这个是完全不符合这个题目的预期的: 上面的做法本身只需要lg(N^2)复杂度;

另外, 我感觉这个二分其实根本没有利用column sorted的性质? 对吧? 结果居然还对的, 居然还是最优复杂度, 想不通;

另外这题应该是可以用一个简单的DP来做的: 每一个entry, leq他的数字全都在他和(0,0)组成的左上角矩形里面; 所以一个DP思路可以把每一个entry的rank都计算出来; 然后这个就不难了; 但是这个是一个N^2的, 不如上面二分来的快; 哦不对, 这个思路不对: 

1   2   3   4  
1   2   3   4  
1   2   3   4  
1   2   3   4

你给(0,3)的rank是4, 但是实际上根本不对;

discussion最优解, 给的两个解法都非常的漂亮:

@YUANGAO1023 said in Share my thoughts and Clean Java Code:

Solution 1 : Heap
Here is the step of my solution:

  1. Build a minHeap of elements from the first row.
  2. Do the following operations k-1 times :
    Every time when you poll out the root(Top Element in Heap), you need to know the row number and column number of that element(so we can create a tuple class here), replace that root with the next element from the same column.

After you finish this problem, thinks more :

  1. For this question, you can also build a min Heap from the first column, and do the similar operations as above.(Replace the root with the next element from the same row)
  2. What is more, this problem is exact the same with Leetcode373 Find K Pairs with Smallest Sums, I use the same code which beats 96.42%, after you solve this problem, you can check with this link:
    https://discuss.leetcode.com/topic/52953/share-my-solution-which-beat-96-42 
public class Solution {  
    public int kthSmallest(int[][] matrix, int k) {  
        int n = matrix.length;  
        PriorityQueue<Tuple> pq = new PriorityQueue<Tuple>();  
        for(int j = 0; j <= n-1; j++) pq.offer(new Tuple(0, j, matrix[0][j]));  
        for(int i = 0; i < k-1; i++) {  
            Tuple t = pq.poll();  
            if(t.x == n-1) continue;  
            pq.offer(new Tuple(t.x+1, t.y, matrix[t.x+1][t.y]));  
        }  
        return pq.poll().val;  
    }  
}  

class Tuple implements Comparable<Tuple> {  
    int x, y, val;  
    public Tuple (int x, int y, int val) {  
        this.x = x;  
        this.y = y;  
        this.val = val;  
    }  

    @Override  
    public int compareTo (Tuple that) {  
        return this.val - that.val;  
    }  
}

第一种思路就是传统的heap解法, 我自己思考的时候的一个坑就是一直纠结于寻找一种类似于diagonal traversal的思路, 但是实际上这个想法方向本身就是一条死路; 仔细看看这个题目给的条件, 是两个方向上面都sorted, 所以你最后想要做到的应该是怎么协调两个方向上的traversal, 而不是想办法走"斜"路;

他这里最后实际上写出来的代码也很直接; 有点像每一个column是一个管子, 然后我们只关注所有的管子的底部, 从底部不停的扔掉最小的一个; 这个算法的correctness应该还是不难理解的, invariant就是每一个iteration被Poll掉的肯定是当前所有剩余的数字里面最小的一个;

那么你说这个人是怎么想到这个解法的? 我们还是一个简单升级的思路(获得思路的一个方式是人逻辑, 这个我们已经证明在这一题并不是立即有效; 另一个方式就是使用简单升级这种类比的方式); 假如我们讨论的是一个一维的sorted array, 那么这个东西其实不难做, 当然你肯定立刻想到2pointer, 但是这里用2pointer并不是立即就有效, 因为这里是找一个kth这样的东西, 即使是一维array里面, 这样一个题型用2pointer做你做过吗?

如果是一个sorted array, 一般我们找kth的方法就很简单, 直接就从开头开始扫, 扫k个就行了; 但是这里我们有的是一个二维的array, 怎么办? 这个时候, 看起来好像一维的做法对于二维的做法并没有什么启示, 但是你应该尝试对一维的做法进行一些进一步的总结和抽象: 一维的做法每一步其实是丢弃当前的所有数字里面的最小值; 那么在二维里面我们也可以实现这样一个思路; 如果直接整个二维array全部sort当然可以, 但是这样一个做法, 对于这个题目明显是overkill了; 我们在每一个iteration关注的其实始终是所有数字里面的最小值; 而我们因为两个方向上都已经sorted, 所以实际上只需要维护N个最小值就行了;

另外注意的是, 假如有一个column已经兜底了, 直接不继续offer这个column就行了, 不需要其他的处理, 因为我们关注的就是global min, 反正这一个column已经兜底了, 那就无关了;

复杂度:

@MadDetective said in Share my thoughts and Clean Java Code:

@lawdawg
The time complexity is O(n + klgn). Yes, the first loop is obviously run just n times, and the final loop is k times the the heap operation. But the worst case is not lg(n^2), because in each loop, it will poll() once, and at most offer()/add() once. So the maximum size of the heap is n. Thus, it is O(n+klgn).

关于PriorityQueue问题的复杂度分析, 核心就是分析PriorityQueue的size, 往往分析的是最大值(但是并不是总是这样, 这里因为size是线性变化//这个分析不对); 进一步, 因为这里是一个循环算法, 所有的东西都是动态变化的, 所以最后你分析的其实就是add和Poll的数量关系;

另外他这里的算法直接就认为是只要size知道是k, 那么直接复杂度肯定就是KlgN, 我感觉还是鲁莽了, 更好的做法应该还是针对add这些操作来分析; 这里有k个add, 每一个add的cost跟size有关, 但是也跟顺序有关; 一开始的刚开始的初始化, 因为是顺序add sorted的, 所以最后就是N的cost; 之后, Poll有K个, 这个不管, 然后add有K个, 每一个都是KlgN, 所以最后是N+KlgN;

有人认为他这里这个算法还可以进一步稍微优化一下:

@eprym said in Share my thoughts and Clean Java Code:

Nice trick, but I think the condition of the first for loop could be changed to 

int bound = matrix.length < k ? matrix.length : k;  
for(int j = 0; j < bound; j++)  {  
    pq.offer(new Tuple(0, j, matrix[0][j]));  
}

意思就是如果K比较小, 那么我们不需要把整个第一行都add进去; 这个其实也就是一个小优化, 你考虑假如K大于N的时候就行了, 这时候最后我们要找的这个kth肯定在第一行里面; 所以在第二个循环根本就不会发生新的add; 2018-04-23 12:30:06 理解的不对, kth并不是一定在第一行里面; 

1   3  
2   4

2th就在第二行里面; 他这个最后想法应该是, kth不可能在(k+1..N)th column里面; 最后只是把右边的一部分矩形给裁掉了而已, 而不是把所有的row都裁掉了;

这个优化的思路还是很直接的, 不过最后有些情况下, 比如K远小于N的时候, 可能效果还是比较明显的;

另外, 这个算法如果你自己写, 你能想到用一个tuple来封装信息吗? 其实你刚开始的想法肯定很简单, 用一个类似row index array的东西来记录每一个column当前的head的位置; 但是你这个方法最后还是逃不过封装; 因为你需要一个基于matrix的entry的value的比较功能(要被持续不停的调用), 但是你同时又需要记录column index, 这个你不封装是做不到的; 2018-04-23 12:32:17 真正面试的时候, 实用要紧, 封装方便就用封装;

Solution 2 : Binary Search
We are done here, but let's think about this problem in another way:
The key point for any binary search is to figure out the "Search Space". For me, I think there are two kind of "Search Space" -- index and range(the range from the smallest number to the biggest number). Most usually, when the array is sorted in one direction, we can use index as "search space", when the array is unsorted and we are going to find a specific number, we can use "range".

Let me give you two examples of these two "search space"

  1. index -- A bunch of examples -- https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/ ( the array is sorted)
  2. range -- https://leetcode.com/problems/find-the-duplicate-number/ (Unsorted Array)

The reason why we did not use index as "search space" for this problem is the matrix is sorted in two directions, we can not find a linear way to map the number and its index. 

public class Solution {  
    public int kthSmallest(int[][] matrix, int k) {  
        int lo = matrix[0][0], hi = matrix[matrix.length - 1][matrix[0].length - 1] + 1;//[lo, hi)  
        while(lo < hi) {  
            int mid = lo + (hi - lo) / 2;  
            int count = 0,  j = matrix[0].length - 1;  
            for(int i = 0; i < matrix.length; i++) {  
                while(j >= 0 && matrix[i][j] > mid) j--;  
                count += (j + 1);  
            }  
            if(count < k) lo = mid + 1;  
            else hi = mid;  
        }  
        return lo;  
    }  
}

这个算法相对就比较讲究一些了; 这个作者还顺带讲解了了一下他自己对于Binary Search的理解; 他认为一种是针对index, 一种是针对range, 其实我认为, Binary Search始终是针对range的(类似于recursion写法里面, 每一个subproblem其实就是一个sub range); 只不过区别在于range of what? 也就分成了index和value;

一般的尤其是一维array的时候, 我们的range直接用index来处理, 但是实际上body里面, 我们的比较这些东西的操作, 实际上还是针对的entry, 只不过因为这里我们的index和value之间有一个准确的对应关系, 所以最后直接就处理index就行了(在处理index和处理value都能成功的情况下, 处理index通常是更方便的, 因为index本身互相之间就是高度规律性的(就是连续的线性的), 而且计算和操作也更方便, 如果真的需要转化成value的时候又是一个direct access就解决了);

但是更加普遍的情况, 这个range处理的应该是value, 就跟这里的一样;

作者自己这样说:

There is no difference between return lo and hi here. The reason is quite simple : my loop invariant is [lo, hi), which means when lo = hi, the loop ends.

这个range他定义的是一个半开半闭的形态, 这个也是一个常见的做法, 不过这里为什么这样做, 我还是没有十足的把握; 不过一个特点是, Binary Search当中, 如果range的定义是半开半闭的情况下, 后面的recursive call的部分往往就只有两个, 而不是三个; 好像这个东西是跟header里面是否取等号是对应的:

  • 如果range是半开半闭: 一般是两个branch, 然后header里面是不取等号;
  • 如果range是全闭区间: 一般是三个branch, 然后header里面取等号;

可以用recursion里面subproblem的思路来稍微帮助理解一下, 一个range其实就对应一个subproblem; 最后header(again, header里面的是yes-condition)判断的就应该是这个range还正常; 所以半开半闭区间就要判断<, 而闭区间就要判断≤; 按照作者自己的解释, 一般半开半闭的区间的做法, 最后lo和hi是相等, 所以不会有一个超界更新的问题, 最后return处理起来更方便; 如果是闭区间的情况, 之前也写过很多次了, 最后往往要对最后一个range进行判断(一般是长度为2的, 也有可能是长度为1的(lo == hi的)), 然后最后termination的时候往往是超界更新, 这个时候分析到底return哪一个就有点麻烦;

与双branch做法对应的, 看他最后对于range的更新方式: 

if(count < k) lo = mid + 1;  
else hi = mid;

这个应该就不难理解了; lo是取得到的, hi是取不到的, 所以一个+1, 一个没有+1;

作为一个Binary Search算法, 一个不变的地方就是, 对于每一个range, 最后实际上作为比较指针的还是mid; 但是这里并没有一个直接的key可以和mid来进行比较, 因为我们这里要做的不是一个find key的操作, 而是一个find kth; 所以最后body里面要做的就是确定, 这个mid跟实际的kth的相对关系;

而确定这个相对关系的唯一的办法, 也就是在整个matrix里面数有多少个数字大于/小于mid; 这个count的过程, 在这个双向sorted的matrix里面, 很意外的O(N)就完成了; 2018-04-23 12:37:38: 为什么是O(N)? 我知道了, 我上面漏看了; 这个做法是利用了column sorted的性质的; count的时候, 对于不同的i, 这个j是统一维护的; 那么这个做法是毫无争议的这题的最优解了; 另外, 这个做法的复杂度是N * lg(N^2), 所以实际上还是NlgN; 能够O(N)时间内完成一个rank(mid)操作, 是这个算法的核心observation;

(j最多移动N(事实上, WorstCase是可能是2N的: 每一个j可能被走两次, 最后有一个类似楼梯一样的visual, 而楼梯两个方向上的位移之和你是知道的, 相加就行了)); 因为是双向sorted, 所以最后我们只要在每一行里面做到这个count就行了(不要总想着把二维的matrix直接降低到零维的点(entry)来处理; 能降低一维就已经不错了); 这里每一个行(每一个i)给count贡献的这个(j+1)其实就是number of entries that is NOT GREATER than mid; 所以最后count就是整个matrix里面≤mid的entry的数量; 注意这里j的更新方式, 每次换行(向下), j是不重置的, 自己想想为什么: 因为如果我们在向下换行的时候, j保持不变, 这个时候下一行这个j后面的所有entry肯定是比mid大的, 这些我们是不用管的; 只用从当前的j位置继续向左移动就行了; 这个技巧也是这个算法的一个点睛之笔;

这个点睛之笔并不是那么容易能想到的(但是又是保证复杂度可以接受的一个关键), 注意看他这里的做法, 当他count ≤ mid的时候, 顺序是从右上角开始, 也就是最小row的最大值开始; 你自己大概在脑子里面枚举一下就可以发现, 这个顺序不是可以随便取的; 要么是从右上角开始, 要么是从左下角开始; 这个是为什么? 首先我们的这个count过程最后要完成的是一个类似用mid来隔开一个row的过程, 你脑子里visual一下; 

*   *   *   * | *  
*   *   * | *   *  
*   *   * | *   *  
*   * | *   *   *  
* | *   *   *   *  
*   *   *   *   *

最后这个mid在没一行的分割位置最后得到的visual就很有可能是这样的一个形状, 这个是由双向sorted这个性质决定的; 我们的目的是做到一个O(N)的复杂度, 就有一个类似KMP那样的, 选择性规避的过程; 最后只有按照这条斜线来走, 才有可能完成一个选择性的规避;

另外这个算法整体的复杂度是多少? 其实不难算, 是2N: 第一个iteration是N, 然后是N/2, 然后是N/2/2, 这个就跟你让你计算一个leaf level是N的BST的node总数一样, 很简单; //不对, 这个算的不对, 首先, 我们的深度其实是lg(N^2), 然后每一个iteration这个N其实是固定更多, 所以最后是N*lg(N^2) = O(NlgN);

另外, 关于最后的这个range的更新, discussion里面一个人给出的说法: 

if(count < k) lo = mid + 1;  
else hi = mid;

image

2018-04-23 12:43:41 大概看看就行了, 这个人第一段对mid是否存在的讨论直接就反了;

当然我个人还是认为没有必要搞得这么复杂的; 他这里这个思路其实就是一个彻底的分情况讨论的过程, 包括这个mid是否确实存在于这个matrix当中(这个其实是一个可能性), 不过我自己理解的时候不是这样理解; 虽然如此, 我思考了一下, 发现了之前半开半闭区间的设定, 其实还是有更深的含义的;

在思考这个问题的时候, 我也意识到, 这里这个作者按照index和range给Binary Search划分的两类其实是非常合理的; 因为虽然我希望用range of index or value这样的表述试图让两种Binary Search进行一个统一的表述, 但是这样其实并不是最好的做法; 当我们写index类型的Binary Search的时候, 我们往往最后要找的是一个index, 或者一个对应的entry, 在这种情况里面, subproblem的概念其实比较强烈, 因为两个index就围成了一个subarray; 而当我们写range类型的Binary Search的时候, 其实我们最后要找的就是一个单纯的value; 那么这个由lo和hi围成的range这里是什么作用呢? 其实就是用来计算mid的, 最后我们希望达到的目的就是让这个range整个缩小到一个数字, 这个数字就是我们想要找到的value;

这种range类的Binary Search最后写的时候, 还往往有一个思考特点, 就是这个range其实跟你在找的这个array, 比如这里的matrix, 是不重合的: 这个range纯粹是为了我们要找的这个value服务的, 它本身跟array的关系并不大; 所以最后你思考的时候就好像这个array跟这个range两者之间是parallel并且隔离的关系; 这个就跟index类的Binary Search差别很大了, 因为这种Binary Search上的这个range本身就是基于这个array定义的;

想了一会儿, 好像我其实并没有理解这个算法? 首先先总结一下这个算法的骨干: 

//find k-th smallest element in a matrix  
lo = min, hi = max + 1;  
while (lo < hi):  
    mid = (lo + hi) / 2;  
    count = number of elements in matrix that is ≤ mid;  
    if (count < k)  
        lo = mid + 1;  
    else  
        hi = mid;  
return lo;

可以用简单升级的思路来帮助理解吗? 这个算法确实是可以原样照搬到一个一维array的问题当中的; 当然了, 如果仅仅是为了在一维当中找kth, 那么这个算法肯定还是比较蠢的; 但是在二维的情况下这个算法就有舞台了;

还是想不通;

2018-04-23 12:20:48
最开始这个heap的做法还是非常直接的; 这题确实无法用sstable那个算法去做, 两个二分搞定; 但是类似kmerge的这个算法, 应该还是能够使用的;

另外我上面对这个做法的解释有点过度解读了; 当时还没有做过kmerge所以理解不了这个做法;

这个是另外一个Binary Search, 虽然背后的原理其实是类似的;

@jiangbowei2010 said in Java 1ms nlog(max -min) solution:

Main loop is binary search of max - min.
Swap from left-bottom to right-top can get count <= mid in O(n) time instead of O(nlogn), total complexity will be O(nlogm) while m = max - min.

2018-04-23 12:45:59 他这个复杂度的分析确实更加准确; 

public class Solution {  
    public int kthSmallest(int[][] matrix, int k) {  
        int n = matrix.length;  
        int lo = matrix[0][0], hi = matrix[n - 1][n - 1];  
        while (lo <= hi) {  
            int mid = lo + (hi - lo) / 2;  
            int count = getLessEqual(matrix, mid);  
            if (count < k) lo = mid + 1;  
            else hi = mid - 1;  
        }  
        return lo;  
    }  

    private int getLessEqual(int[][] matrix, int val) {  
        int res = 0;  
        int n = matrix.length, i = n - 1, j = 0;  
        while (i >= 0 && j < n) {  
            if (matrix[i][j] > val) i--;  
            else {  
                res += i + 1;  
                j++;  
            }  
        }  
        return res;  
    }  
}

2018-04-23 12:46:22 看到没, 闭区间做法是完全没有问题的; 关键就是这个等于的情况, 你怎么处理; 开区间还是闭区间只要对应header写的对能terminate就行了, 不是这题的核心; 另外闭区间写法照样可以二叉, 所以这个也不能死板的记忆;

区别主要在于他这里的range的更新方式, hi的更新是-1了, 然后header里面判断的是可以取等号, 他这个情况实际上最后这个range就是一个闭区间了; 我之前还刚想说是不是range类的Binary Search最好都用半开半闭的区间, 这里看看人家这里用闭区间也是能做的; 不过看起来range类的Binary Search到目前还是有一个共同点, 就是都是2branch的结构;

也就是说:

  • range类Binary Search与2branch对应; index类Binary Search与3branch对应(不过好像很多时候2branch也可以做, 就是稍微麻烦一点);
  • 半开半闭区间与header不取等号对应; 如果是闭区间, 无论是几branch, 基本header都要取等号;

注意他这里这个traverse走的其实还是上面说过的那个对角线, 不过他是从左下角开始走; 而且他这个写法, 相对于之前那个人的写法来说, 逐行扫描的概念更加薄弱, 而是强调一个单纯的对i和j的更新完成traverse, 感觉这样的一个traverse写法实际上可能是更符合出题人的意图的;

2018-04-23 12:48:31 这样的一个双向移动来维护(i, j), 实际上我觉得代码反而好理解一些;

在这个解法下面, 关于为什么最后找到的lo一定在matrix里面:

@zipte89 said in Java 1ms nlog(max -min) solution:

@xuefei1 Adding on to @luofei 's answer. The element found by this algorithm has to be in the input matrix because the range converges to the minimum value that satisfies (or most closely follows) the condition count == k. The first value to satisfy count == k must be found in the range if exists.

这个解释就非常的好了, 而且也充分的理解了这个问题里面range类Binary Search的独特性;

又仔细想了一下, 好像这个解释并不完整? 这里说会converge to the min that satisfies, 这个又是哪里来的呢? 2018-04-23 12:49:23 依然认为这个解释不完整, 还是一个因为正确所以正确的论断方式; 不过他这个converge to the min概念, 其实是以前见过的: 三叉转二叉的时候, 等于的情况扔在哪边, 最后实际上对应的是, 当等于有多个存在的时候, 选择leftmost还是rightmost; 如果要leftmost, 就往左边扔, 让他从左边向右弹回来, 得到的就是leftmost hit; 对应的, 要rightmost, 就往右边扔;

Invariant of Binary Search

感觉理解这个算法, 跟理解大部分的Binary Search的算法的时候的核心, 都是要找到一个有效的invariant;

但是这里的这个算法作为一个range类的Binary Search, 这个invariant其实并不好找. 在index类的Binary Search里面, 因为有这个subproblem的概念, 所以很多时候invariant的概念比较具体; 但是在这里, 我们这个range其实完全就是为mid这一个value来服务的; subproblem的概念很模糊, invariant相对也不好找;

这个是另外一个解释:

@ngale said in Java 1ms nlog(max -min) solution:

@xuefei1 I have read comments from both @luofei and @zipte89, but I still could not get it. Then, I thought a prove like below:

If the mid variable converges to an integer, a_mid, which is not the kth smallest element, a_k, in the array.
Then, a_mid should be bigger than a_k, if not the count will be less than k and a_mid will increase.
Therefore, lo<=a_k<a_mid<=hi will be true, and the loop ends at lo=hi, which means a_mid has to equal to a_k.

Looks like a squeeze theorem.

更加学究一点, 夹逼定理, 不过总体的思路好像还是对的; 反证法, 该想到的(主要好像还是潜意识里面怕麻烦了, 想要用一个更加intuitive的方法得到这个结论); 事实上, 后来发现, 这个解释其实更好理解一些; 上面那个解释看起来很intuitive, 实际上最后还是太飘了;

另外, 这个算法当时让我很不理解的时候, 是假如一开始就找到的这个mid的count就是k, 会怎么样? 这个时候hi其实就会保持不动了, 然后lo会一直向右移动, 直到重合; 这个过程看起来就有点奇怪, 为什么不干脆直接3branch加一个hit case呢; 当然, 如果加了, 成了一个3branch, 假如我们第一个找到的mid就是一个count等于k的, 你就能break吗? 当然不能, 这个mid才是正儿八经的有可能不在matrix里面; 所以这个算法本身应该还是有点玄机在里面的;

另外这个分析也看出来一个问题, 3branch的写法, 其实很多时候寻求的是hit, 而2branch的写法, 更多的时候是靠的收敛; hit的思路有时候确实可以让termination的判断更加直接和简单, 但是有些情况hit的写法未必能够解决, 而收敛的写法基本是可以保证成功的;

另外, 这个人提出的lo<=a_k<a_mid<=hi这个东西, 其实可以当做是一个invariant; 不过一个看起来这么简单的小算法的invariant真的会这么复杂吗? 还要引入a_k这么个东西?

仔细思考了一下这个问题(这个问题实在是太抽象了, 一个思考的关键就是脑子里要找到合适的visual; 我用的visual就是一大堆的鸡蛋排成一个array(因为这里维度并不是主要矛盾, 所以我就用简单的一维来帮助思考这个Binary Search的框架), 然后如果mid是在array里面的, 就用一个绿鸡蛋来表示, 否则就是红鸡蛋); //后来发现可以用键盘来帮助思考;

在问了一下guoye之后, 得到一个重要信息: 我最后要找的这个kth肯定一直在[lo, hi)里面; 好像应该是始终位于[lo, hi]里面(假如一开始找到的mid就等于某一个鸡蛋, 并且这个鸡蛋正好就是kth, 那么后面的iteration里面, 这个kth鸡蛋是始终都不在[lo,hi)里面的); 这个是他的论断:

元素要么在lo..mid，要么在mid..hi，mid变成新的hi或新的lo，保证元素始终在lo..hi

2018-04-23 12:53:28 这个跟我上面的扔到左边反弹的思路是有点类似的;

感觉他想问题还是很直接准确; 这个有点类似enumeration的思路; 不过我回头想了一下, 他这个理解方式其实并没有很完整的涵盖到这个问题本身的一些细节上的peculiarity;

还是想不通;

感觉这个就是range类Binary Search的难点了, 这个contains问题; 因为你现在搜索的是value, 你很难保证你取mid取到的这个value就真的实际上存在; 当然这个算法最后看来, 是没有什么好难保证的, 只是我自己还没有理解而已;

Stefan貌似看了一个paper之后写了一个更快的解法:

@StefanPochmann said in O(n) from paper. Yes, O(#rows).:

It's O(n) where n is the number of rows (and columns), not the number of elements. So it's very efficient. The algorithm is from the paper Selection in X + Y and matrices with sorted rows and columns, which I first saw mentioned by @elmirap (thanks).

The basic idea: Consider the submatrix you get by removing every second row and every second column. This has about a quarter of the elements of the original matrix. And the k-th element (k-th smallest I mean) of the original matrix is roughly the (k/4)-th element of the submatrix. So roughly get the (k/4)-th element of the submatrix and then use that to find the k-th element of the original matrix in O(n) time. It's recursive, going down to smaller and smaller submatrices until a trivial 2×2 matrix. For more details I suggest checking out the paper, the first half is easy to read and explains things well. Or @zhiqing_xiao's solution+explanation.

Cool: It uses variants of saddleback search that you might know for example from the Search a 2D Matrix II problem. And it uses the median of medians algorithm for linear-time selection.

Optimization: If k is less than n, we only need to consider the top-left k×k matrix. Similar if k is almost n2. So it's even O(min(n, k, n^2-k)), I just didn't mention that in the title because I wanted to keep it simple and because those few very small or very large k are unlikely, most of the time k will be "medium" (and average n2/2).

Implementation: I implemented the submatrix by using an index list through which the actual matrix data gets accessed. If [0, 1, 2, ..., n-1] is the index list of the original matrix, then [0, 2, 4, ...] is the index list of the submatrix and [0, 4, 8, ...] is the index list of the subsubmatrix and so on. This also covers the above optimization by starting with [0, 1, 2, ..., k-1] when applicable.

Application: I believe it can be used to easily solve the Find K Pairs with Smallest Sums problem in time O(k) instead of O(k log n), which I think is the best posted so far. I might try that later if nobody beats me to it (if you do, let me know :-). Update: I did that now. 

class Solution(object):  
    def kthSmallest(self, matrix, k):  

        # The median-of-medians selection function.  
        def pick(a, k):  
            if k == 1:  
                return min(a)  
            groups = (a[i:i+5] for i in range(0, len(a), 5))  
            medians = [sorted(group)[len(group) / 2] for group in groups]  
            pivot = pick(medians, len(medians) / 2 + 1)  
            smaller = [x for x in a if x < pivot]  
            if k <= len(smaller):  
                return pick(smaller, k)  
            k -= len(smaller) + a.count(pivot)  
            return pivot if k < 1 else pick([x for x in a if x > pivot], k)  

        # Find the k1-th and k2th smallest entries in the submatrix.  
        def biselect(index, k1, k2):  

            # Provide the submatrix.  
            n = len(index)  
            def A(i, j):  
                return matrix[index[i]][index[j]]  

            # Base case.  
            if n <= 2:  
                nums = sorted(A(i, j) for i in range(n) for j in range(n))  
                return nums[k1-1], nums[k2-1]  

            # Solve the subproblem.  
            index_ = index[::2] + index[n-1+n%2:]  
            k1_ = (k1 + 2*n) / 4 + 1 if n % 2 else n + 1 + (k1 + 3) / 4  
            k2_ = (k2 + 3) / 4  
            a, b = biselect(index_, k1_, k2_)  

            # Prepare ra_less, rb_more and L with saddleback search variants.  
            ra_less = rb_more = 0  
            L = []  
            jb = n   # jb is the first where A(i, jb) is larger than b.  
            ja = n   # ja is the first where A(i, ja) is larger than or equal to a.  
            for i in range(n):  
                while jb and A(i, jb - 1) > b:  
                    jb -= 1  
                while ja and A(i, ja - 1) >= a:  
                    ja -= 1  
                ra_less += ja  
                rb_more += n - jb  
                L.extend(A(i, j) for j in range(jb, ja))  

            # Compute and return x and y.  
            x = a if ra_less <= k1 - 1 else \  
                b if k1 + rb_more - n*n <= 0 else \  
                pick(L, k1 + rb_more - n*n)  
            y = a if ra_less <= k2 - 1 else \  
                b if k2 + rb_more - n*n <= 0 else \  
                pick(L, k2 + rb_more - n*n)  
            return x, y  

        # Set up and run the search.  
        n = len(matrix)  
        start = max(k - n*n + n-1, 0)  
        k -= n*n - (n - start)**2  
        return biselect(range(start, min(n, start+k)), k, k)[0]

因为是Python, 而且贼复杂, 所以就没有看了; 而且Stefan自己也说了, 这个解法在实际的面试当中并不一定有多大的价值, 而且average case的情况下, 这个算法的复杂度好像并没有超出上面的那个Binary Search很多;

这个是一个C++版本的:

@zhiqing_xiao said in C++ O(n)-time O(n)-space solution with detail intuitive explanation:

This thread is inspired by @StefanPochmann's thread, which mentioned Mirzaian and Arjoandi's paper.

Preparations

  1. When n==1 (i.e. the matrix is 1x1. n is the number of row), the problem is trival. Hencefore we only consider the case n>=2.
  2. Rather than finding one k-th element from the matrix, we will select TWO elements (say, k0-th element and k1-th element) simultaneously, such that 0<=k0<=k1<n*n and k1-k0<=4n. Obviously, if we can complete the aforementioned selection in O(n), we can find the k-th element in O(n) by simply letting k=k0=k1.
    Let x0 denote the k0-th element; let x1 denote the k1-th element. Obviously we have x0<=x1.

Now we will introduce how to select x0 and x1 in O(n).

General idea:
For an nxn matrix, where n is large, we try to select x0 and x1 in a recursive way.

  1. (Determine submatrix) This step constructs one submatrix, whose number of elements will be approximately a quarter of the original matrix. The submatrix is defined as every other row and every other column of the original matrix. The last row and the last column are included too (the reason will be stated in the sequel.) Then the dimension of the matrix is approximately (n/2) x (n/2). The submatrix is recorded by the indices in the original matrix.
    Example 1: the original matrix has indices {0, 1, 2, 3, 4}, then the submatrix has indices {0, 2, 4}.
    Example 2: the original matrix has indices {0,1, 2, 3, 4, 5}, then the submatrix has indices {0, 2,4, 5}.

  2. (Determine new k's) This step determines two new k's (denoted as k0_ and k1_) such that (i) k0_ is the largest possible integer to ensure k0_-th element in the new submatrix (denoted as x0_) is not greater than x0; (ii) k1_ is the smallest possible integer to ensure k1_-th element in the new submatrix (denoted as x1_) is not less than x1. This step is the most tricky step.

    k0 = floor(k0 / 4)
    k1     = floor(k1 / 4) + n + 1 (when n is even) 

        floor((k1 + 2 * n + 1) / 4) (when n is odd)

The picture can also be founded here.

Recall that we mentioned the last row and column shall always be included in the matrix. That is to ensure we can always found the x1_ such that x1_ >= x1.

  1. (Call recursively) Obtainx0_ and x1_ by recursion.
  2. (Partition) Partition all elements in the original nxn elements into three parts: P1={e: e < x0_}, P2={e: x0_ <= e < x1_ }, P3={e: x1_ < e}. We only need to record the cardinality of P1 and P2 (denoted as |P1| and |P2| respectively), and the elements in P2. Obviously, the cardinality of P2 is O(n).
  3. (Get x0 and x1) From the definition of k0_ and k1_, we have |P1| < k0 <= |P1|+|P2|. When |P1| < k0 < |P1|+|P2|, x0 is the k0-|P1|-th element of P2; otherwise x0=x1_. x1 can be determined in a similar way. This action is also O(n).

Complexities:

  • Time: O(n) ----- Apply T(n) = T(n/2) + O(n) in the Master's Theorem.
  • Space: O(n)

C++ Accepted Code: 

class Solution {  
public:  
   int kthSmallest(const std::vector<std::vector<int>> & matrix, int k)  
   {  
       if (k == 1) // guard for 1x1 matrix  
       {  
           return matrix.front().front();  
       }  

       size_t n = matrix.size();  
       std::vector<size_t> indices(n);  
       std::iota(indices.begin(), indices.end(), 0);  
       std::array<size_t, 2> ks = { k - 1, k - 1 }; // use zero-based indices  
       std::array<int, 2> results = biSelect(matrix, indices, ks);  
       return results[0];  
   }  

private:  
   // select two elements from four elements, recursively  
   std::array<int, 2> biSelect(  
       const std::vector<std::vector<int>> & matrix,  
       const std::vector<size_t> & indices,  
       const std::array<size_t, 2> & ks)  
   // Select both ks[0]-th element and ks[1]-th element in the matrix,  
   // where k0 = ks[0] and k1 = ks[1] and n = indices.size() satisfie  
   // 0 <= k0 <= k1 < n*n  and  k1 - k0 <= 4n-4 = O(n)   and  n>=2  
   {  
       size_t n = indices.size();        
       if (n == 2u) // base case of resursion  
       {             
           return biSelectNative(matrix, indices, ks);  
       }  

       // update indices  
       std::vector<size_t> indices_;  
       for (size_t idx = 0; idx < n; idx += 2)  
       {  
           indices_.push_back(indices[idx]);  
       }  
       if (n % 2 == 0) // ensure the last indice is included  
       {  
           indices_.push_back(indices.back());  
       }  

       // update ks  
       // the new interval [xs_[0], xs_[1]] should contain [xs[0], xs[1]]  
       // but the length of the new interval should be as small as possible  
       // therefore, ks_[0] is the largest possible index to ensure xs_[0] <= xs[0]  
       // ks_[1] is the smallest possible index to ensure xs_[1] >= xs[1]  
       std::array<size_t, 2> ks_ = { ks[0] / 4, 0 };  
       if (n % 2 == 0) // even  
       {  
           ks_[1] = ks[1] / 4 + n + 1;  
       }  
       else // odd  
       {  
           ks_[1] = (ks[1] + 2 * n + 1) / 4;  
       }  

       // call recursively  
       std::array<int, 2> xs_ = biSelect(matrix, indices_, ks_);  

       // Now we partipate all elements into three parts:  
       // Part 1: {e : e < xs_[0]}.  For this part, we only record its cardinality  
       // Part 2: {e : xs_[0] <= e < xs_[1]}. We store the set elementsBetween  
       // Part 3: {e : x >= xs_[1]}. No use. Discard.  
       std::array<int, 2> numbersOfElementsLessThanX = { 0, 0 };  
       std::vector<int> elementsBetween; // [xs_[0], xs_[1])  

       std::array<size_t, 2> cols = { n, n }; // column index such that elem >= x  
        // the first column where matrix(r, c) > b  
        // the first column where matrix(r, c) >= a  
       for (size_t row = 0; row < n; ++row)  
       {  
           size_t row_indice = indices[row];  
           for (size_t idx : {0, 1})  
           {  
               while ((cols[idx] > 0)  
                   && (matrix[row_indice][indices[cols[idx] - 1]] >= xs_[idx]))  
               {  
                   --cols[idx];  
               }  
               numbersOfElementsLessThanX[idx] += cols[idx];  
           }  
           for (size_t col = cols[0]; col < cols[1]; ++col)  
           {  
               elementsBetween.push_back(matrix[row_indice][indices[col]]);  
           }  
       }  

       std::array<int, 2> xs; // the return value  
       for (size_t idx : {0, 1})  
       {  
           size_t k = ks[idx];  
           if (k < numbersOfElementsLessThanX[0]) // in the Part 1  
           {  
               xs[idx] = xs_[0];  
           }  
           else if (k < numbersOfElementsLessThanX[1]) // in the Part 2  
           {  
               size_t offset = k - numbersOfElementsLessThanX[0];  
               std::vector<int>::iterator nth = std::next(elementsBetween.begin(), offset);  
               std::nth_element(elementsBetween.begin(), nth, elementsBetween.end());  
               xs[idx] = (*nth);  
           }  
           else // in the Part 3  
           {  
               xs[idx] = xs_[1];  
           }  
       }  
       return xs;  
   }  

   // select two elements from four elements, using native way  
   std::array<int, 2> biSelectNative(  
       const std::vector<std::vector<int>> & matrix,  
       const std::vector<size_t> & indices,  
       const std::array<size_t, 2> & ks)  
   {  
       std::vector<int> allElements;  
       for (size_t r : indices)  
       {  
           for (size_t c : indices)  
           {  
               allElements.push_back(matrix[r][c]);  
           }  
       }  
       std::sort(allElements.begin(), allElements.end());  
       std::array<int, 2> results;  
       for (size_t idx : {0, 1})  
       {  
           results[idx] = allElements[ks[idx]];  
       }  
       return results;  
   }  
};

贼鸡儿吓人, 再说了;

除开这些这个问题基本没有更好的算法了; 不过这个Binary Search真的是让人很回味好吧;

Problem Description

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example: 

matrix = [  
   [ 1,  5,  9],  
   [10, 11, 13],  
   [12, 13, 15]  
],  
k = 8,  

return 13.

Note:

  • You may assume k is always valid, 1 ≤ k ≤ n^2.

Difficulty:Medium
Total Accepted:41.2K
Total Submissions:92.1K
Contributor: LeetCode
Companies
google twitter
Related Topics
binary search heap
Similar Questions
Find K Pairs with Smallest Sums Kth Smallest Number in Multiplication Table

results matching ""

    No results matching ""