leetcode_378

发表于   |   分类于

Kth Smallest Element in a Sorted Matrix

题目戳这

题意

给定一个矩阵，行有序，列有序，问你这个矩阵中第k小的数字是多少。

解法

因为有序，所以我们可以用二分，在这里我们在二维数组中进行二分。首先取矩阵中的最小值和最大值，分别为矩阵的最左上角和最右下角。然后二分，二分出来的值，我们在矩阵中寻找比它小或者等于的数，寻找的时候我们对行进行遍历，列的话我们先从最右边开始，逐渐减少即可，因为这个矩阵它是符合行从小到大有序和列从小到大有序的规则的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
    def kthSmallest(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        n = len(matrix)
        #print(n)
        lt = matrix[0][0]
        rt = matrix[n-1][n-1]
        
        while lt < rt:
            mid = lt+(rt-lt)//2
            ct = 0
            j = n-1
            for i in range(n):
                while j >= 0 and matrix[i][j] > mid: # look for the first matrix[i][j] <= mid
                    j -= 1
                ct += (j+1)
            if ct < k:
                lt = mid + 1
            else:
                rt = mid
        
        return lt