【Leetcode】378. Kth Smallest Element in a Sorted Matrix 解题报告

二维矩阵每行每列都是单调增的，求矩阵中第K小个元素

方法1：使用堆

第K小问题首先想到的应该是堆排序。对于求第K小问题，我们只需要维护一个包含k个元素的最大堆，这样最后堆顶元素就是第k小个元素。
考虑如何维护一个大小为K的堆

• 首先，当堆的大小小于k时，我们要能在堆的末尾添加新的元素，然后通过上浮操作把新添加的元素调整到适合的为位置
• 当堆的大小为k时，如果新加入的元素大于堆顶元素，就舍弃。因为堆中当前维护的是最小的k个元素，所以新来一个比这个k个元素最大的还要大，就不然他加入。否则，将堆顶元素换成该元素，并通过下沉的方法将堆调整到满足堆性质的状态

class Solution:
    def kthSmallest(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype
        """
        #建立一个最大堆
        self.heap = [0]
        for row in matrix:
            for ele in row:
                self.insert_heap(ele,k)
                print(self.heap)

        return self.heap[1]

    def insert_heap(self, number,k):
        # print(self.heap[0],k)
        if self.heap[0] < k:
            self.heap[0] += 1
            self.heap.append(number)
            self.flow_up()
        else:
            if number < self.heap[1]:
                self.heap[1] = number
                self.sink_in()
                
    def flow_up(self):
        flow_node_index = len(self.heap)-1
        parent_index = flow_node_index // 2
        while(parent_index > 0):
            if self.heap[parent_index] < self.heap[flow_node_index]:
                self.heap[parent_index],self.heap[flow_node_index] = self.heap[flow_node_index],self.heap[parent_index]
            else:
                break
            flow_node_index = parent_index
            parent_index = flow_node_index // 2

    def sink_in(self):
        sink_node_index= 1
        while(True):
            left_child = sink_node_index*2
            right_child = left_child +1
            if left_child > self.heap[0]:
                break
            if right_child > self.heap[0]:
                maxchild = left_child
            else:
                maxchild = left_child if self.heap[left_child] > self.heap[right_child] else right_child
            if self.heap[maxchild] < self.heap[sink_node_index]:
                    break
            self.heap[maxchild],self.heap[sink_node_index] = self.heap[sink_node_index],self.heap[maxchild]
            sink_node_index = maxchild

方法2：二分查找

使用二分法进行查找，拿题目给的例子为例

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

首先low =1,high =15,mid = (1+high)//2 = 8，我们找出小于等于8的元素有多少个。
怎么找呢，对于每一行我们可以用二分法查找出小于等于8的元素有多少，然后求和。
比如第一次二分我们得到的值是sum(2,0,0)=2,
如果得到的sum < k,(注意这里不能写<=)，说明8这个中间值小了，所以要扩大范围，令low= mid+1,否则low=mid。

step1: low = 1, high = 15, mid =8, sum = (2,0,0) = 2
step2: low = 9, high =15,  mid = 12, sum =(3,2,1) = 6
step3: low = 13, high = 15, mid = 14, sum = (3, 3,2) =8

我们的递归终止的条件是 low >= high,此时虽然找到了适合的mid,但这个mid=14，不在数组中，我们继续缩小范围
此时14满足条件但不在数组中，我们要向下搜寻（因为上面我们求的是小于等于xx的个数）

step4: low = 13, high =14,  mid = 13, sum =(3,3,2) = 8
step5: low = 13, high = 13,  mid = 13, sum = (3, 3,2) =8
因为 low == high ,查找结束

直到找到了满足条件的mid值。最终low或者high 或者mid是无限逼近我们要找的那个二维数组中的元素,这里循环能终止，是因为我们用了整除，会导致low和high相等，否则永远也不会停止，只会越来越逼近我们要查找的那个数。所以该方法个人认为还是有一定的局限性。
AC代码

class Solution:
    def kthSmallest(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        low = matrix[0][0]
        high = matrix[-1][-1]
        while(low < high):
            mid = (low+high)//2
            if sum(self.FindRightIndex(row, mid) for row in matrix) < k:
                low = mid+1
            else:
                high = mid
        return low

    def FindRightIndex(self,array, element):
        if element < array[0]:
            return 0
        if element >= array[-1]:
            return len(array)
        low = 0
        high = len(array) - 1
        while (low < high):
            # print(low, high)
            mid = (low + high) // 2
            if high - low == 1 and array[low] <= high < array[high]:
                return high
            elif array[mid] <= element:
                low = mid + 1
            else:
                high = mid
        return high

方法3

O(n)的时间复杂度，而且n是二维矩阵的行数，理论依据是这篇论文
http://www.cse.yorku.ca/~andy/pubs/X+Y.pdf
这种方法日后有时间再研究了