LeetCode 378. Kth S Element in a Sorted Matrix

简介: 给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小的元素。请注意,它是排序后的第k小元素,而不是第k个元素。

v2-4abfd2f30533c79bd4fa06ff22bef51d_1440w.jpg

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.


描述



给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小的元素。

请注意,它是排序后的第k小元素,而不是第k个元素。


示例:


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


来源:力扣(LeetCode)

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

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


思路



思路一


  • 使用堆,维护一个最大堆,限定堆中的元素个数为 k ,将所有的元素依次压入堆中,当堆中元素大于 k 时,pop 出最大的元素。堆中最后一个元素即是所有。
  • python3 没有实现最大堆而是实现了最小堆,我们将每一个数乘以 -1,使用最小堆来模拟最大堆。


import heapq
from typing import List
class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        count_row, count_col = len(matrix), len(matrix[0])
        if not matrix:
            return 0
        heap = []
        for i in range(count_row):
            for j in range(count_col):
                heapq.heappush(heap, -matrix[i][j])
                if len(heap) > k:
                    heapq.heappop(heap)
        return -heap[0]


思路二


  • 使用二分法,二分的对象是数组中数字的大小范围。
  • 其基本思路是:small,big 分别表示数组中最小和最大的数,midlle = (small + big)//2,统计数组中小于等于 midlle 元素的个数,记为 count;如果 count 大于等于 k,说明第 k 大的数 在 small 到 big 之间;如果 count 小于 k,说明第 k 大的数应该在 middle+1 到 big 之间;不断利用二分法,直到 small == big,此时一定有数组小于等于 small 数的个数为 k;
  • 关于如何统计数组中小于的等于 k 的数,利用了 leetcode 第 74 题 Search a 2D Matrix 的思想,其解析在这里


from typing import List
class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        small, big = matrix[0][0], matrix[-1][-1]
        while small < big:
            middle = small + ((big - small) >> 1)
            count = self.less_eq_than_k(matrix, middle)
            if count >= k:
                big = middle
            if count < k:
                small = middle + 1
        return small
    def less_eq_than_k(self, matrix: List[List[int]], middle: int) -> int:
        count, i, j = 0, 0, len(matrix[0]) - 1
        while i < len(matrix) and j >= 0:
            if matrix[i][j] <= middle:
                count += j + 1
                i += 1
            else:
                j -= 1
        return count

源代码文件在 这里


目录
相关文章
|
8月前
Leetcode 74. Search a 2D Matrix
这道题很简单,为此专门写篇博客其实算博客凑数了。给你一个每一行每一列都是增序,且每一行第一个数都大于上一行末尾数的矩阵,让你判断某个数在这个矩阵中是否存在。 假设矩阵是m*n,扫一遍的时间复杂度就是O(m*n),题目中给出的这么特殊的矩阵,时间复杂度可以降到O(m+n),具体代码如下,写的比较挫。
67 1
|
8月前
Leetcode 240. Search a 2D Matrix II
具体思路就是每一行倒着扫,扫到第一个比target小的数就跳到下行,如果等于当然是直接返回true了,如果下一行还比target小就继续跳下一行,直到最后一行。 为啥这么做是可行的? 可能我比较笨,想了半天才想到。 因为每一列都是增序的,举个例子,假设matrix[0][5] > target,那么[0][5]位置右下(包含右和下)所有元素不可能比target小。
33 0
|
8月前
Leetcode 230. Kth Smallest Element in a BST
先来看下二叉搜索树的性质,对于任意一个非叶子节点,它的左子树中所有的值必定小于这个节点的val,右子树中所有的值必定大于或等于当前节点的val。 这条性质就保证了如果我们对二叉搜索树做中序遍历,中序遍历的结果肯定是有序的。对于此题而言,我们只需要拿到中序遍历结果,然后返回第k个即可,时间复杂度是O(n)。
51 1
|
8月前
Leetcode 4. Median of Two Sorted Arrays
题目描述很简单,就是找到两个有序数组合并后的中位数,要求时间复杂度O(log (m+n))。 如果不要去时间复杂度,很容易就想到了归并排序,归并排序的时间复杂度是O(m+n),空间复杂度也是O(m+n),不满足题目要求,其实我开始也不知道怎么做,后来看了别人的博客才知道有个二分法求两个有序数组中第k大数的方法。
19 0
|
8月前
Leetcode Find Minimum in Rotated Sorted Array 题解
对一个有序数组翻转, 就是随机取前K个数,移动到数组的后面,然后让你找出最小的那个数,注意,K有可能是0,也就是没有翻转。
29 0
LeetCode 167 Two Sum II - Input array is sorted(输入已排序数组,求其中两个数的和等于给定的数)
给定一个有序数组和一个目标值 找出数组中两个成员,两者之和为目标值,并顺序输出
67 0
|
算法 Python
LeetCode 108. 将有序数组转换为二叉搜索树 Convert Sorted Array to Binary Search Tree
LeetCode 108. 将有序数组转换为二叉搜索树 Convert Sorted Array to Binary Search Tree
|
算法 测试技术
LeetCode 88. 合并两个有序数组 Merge Sorted Array
LeetCode 88. 合并两个有序数组 Merge Sorted Array
LeetCode 21. 合并两个有序链表 Merge Two Sorted Lists
LeetCode 21. 合并两个有序链表 Merge Two Sorted Lists
LeetCode 1380. 矩阵中的幸运数 Lucky Numbers in a Matrix
LeetCode 1380. 矩阵中的幸运数 Lucky Numbers in a Matrix