【BinarySearch】378. Kth Smallest Element in a Sorted Matrix

题目链接:https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/description/

 

 

 

给一个n*n的二维数组matrix , 它的所有行和列都是升序排列。求这个矩阵中第k小的数。

 

 

  • 第一种办法是二分。  二分有两种搜索方式,一是按索引分。 而是按照数据的范围分。  对一个排好序的一维数组采用第一种方式。否则按照范围分。本题只能按照数据范围分

将所给数据的最小值和最大值作为low 和high 。 搜索判断mid值是否满足第k小的条件。    本题由于行列都有序。判断时可以加快速度。  复杂度o((m+n)*logn)

 

 

 

  • 第二种方法是最小堆。(来自discuss
    java提供的PriorityQueue集合内部实现为最小堆数据结构。   先用二维数组第一行创建堆。 执行k-1 次的出堆,入堆操作。  每一次入堆只需要插入上一次取出的元素相同列的下一行即可。因为下一个最小值只可能在其下一个元素和当前堆中元素产生。      所以这里需要记录元素的行和列标号。  定义一个Tuple类。               第k次出堆的数就是第k小。   (最坏复杂度k*logK)