【Day 89 】2023-09-06 - 378. 有序矩阵中第 K 小的元素

[azl397985856]

378. 有序矩阵中第 K 小的元素

入选理由

暂无

题目地址

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

前置知识

• 二分查找
• 堆

  题目描述

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

 

示例：

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

返回 13。  

提示： 你可以假设 k 的值永远是有效的，1 ≤ k ≤ n2 。

[Diana21170648]

思路

堆二分找有序矩阵中的第K小

代码

class Solution:
    def notGreaterCount(self, matrix, target):
        # 等价于在matrix中搜索mid，搜索的过程中利用有序的性质记录比mid小的元素个数

        # 我们选择左下角，作为开始元素
        curRow = 0
        # 多少列
        COL_COUNT = len(matrix[0])
        # 最后一列的索引
        LAST_COL = COL_COUNT - 1
        res = 0

        while curRow < len(matrix):
            # 比较最后一列的数据和target的大小
            if matrix[curRow][LAST_COL] < target:
                res += COL_COUNT
            else:
                i = COL_COUNT - 1
                while i >= 0 and matrix[curRow][i] > target:
                    i -= 1
                # 注意这里要加1
                res += i + 1
            curRow += 1

        return res

    def kthSmallest(self, matrix, k):
        if len(matrix) < 1:
            return None
        start = matrix[0][0]
        end = matrix[len(matrix) - 1][len(matrix[0]) - 1]
        while start < end:
            mid = start + ((end - start) >> 1)
            count = self.notGreaterCount(matrix, mid)
            if count < k:
                start = mid + 1
            else:
                end = mid
        # 返回start，mid，end都一样
        return start

复杂度分析

• 时间复杂度：O(Nlog（r-l）)，其中 N 为数组长度。
• 空间复杂度：O(1)

[Beanza]

class Solution: def notGreaterCount(self, matrix, target):

等价于在matrix中搜索mid，搜索的过程中利用有序的性质记录比mid小的元素个数

    # 我们选择左下角，作为开始元素
    curRow = 0
    # 多少列
    COL_COUNT = len(matrix[0])
    # 最后一列的索引
    LAST_COL = COL_COUNT - 1
    res = 0

    while curRow < len(matrix):
        # 比较最后一列的数据和target的大小
        if matrix[curRow][LAST_COL] < target:
            res += COL_COUNT
        else:
            i = COL_COUNT - 1
            while i >= 0 and matrix[curRow][i] > target:
                i -= 1
            # 注意这里要加1
            res += i + 1
        curRow += 1

    return res

def kthSmallest(self, matrix, k):
    if len(matrix) < 1:
        return None
    start = matrix[0][0]
    end = matrix[len(matrix) - 1][len(matrix[0]) - 1]
    while start < end:
        mid = start + ((end - start) >> 1)
        count = self.notGreaterCount(matrix, mid)
        if count < k:
            start = mid + 1
        else:
            end = mid
    # 返回start，mid，end都一样
    return start

[passengersa]

代码： /**

• @param {number[][]} matrix
• @param {number} k

• @return {number} */ var kthSmallest = function(matrix, k) { var nums = []; var temp = 0; for (var i = 0; i < matrix.length; i++) { for (var j = 0; j < matrix[i].length; j++) { nums.push(matrix[i][j]) } }

  for (var i = 0; i < nums.length; i++) { for (var j = i + 1; j < nums.length; j++) { if (nums[i] > nums[j]) { temp = nums[i]; nums[i] = nums[j]; nums[j] = temp } } } console.log(nums) return (nums[k - 1]) };

[Fuku-L]

代码

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                return a[0] - b[0];
            }
        });
        int n = matrix.length;
        for(int i = 0; i<n; i++){
            pq.offer(new int[]{matrix[i][0], i, 0});
        }
        for(int i = 0; i<k-1; i++){
            int[] now = pq.poll();
            if(now[2] != n - 1){
                pq.offer(new int[]{matrix[now[1]][now[2]+1], now[1], now[2]+1});
            }
        }
        return pq.poll()[0];
    }
}

[yetfan]

代码

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        n = len(matrix)

        def check(mid):
            i, j = n - 1, 0
            num = 0
            while i >= 0 and j < n:
                if matrix[i][j] <= mid:
                    num += i + 1
                    j += 1
                else:
                    i -= 1
            return num >= k

        left, right = matrix[0][0], matrix[-1][-1]
        while left < right:
            mid = (left + right) // 2
            if check(mid):
                right = mid
            else:
                left = mid + 1

        return left

[Alexno1no2]

# # 最大堆
# # 遍历矩阵元素依次入堆，堆的大小为k，存储的是遍历到目前为止的k个较小值
# # 如果堆的大小一旦大于k，弹出堆顶元素，让堆的大小维持为k
# # 遍历完后，返回堆顶元素

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

# 二分查找
# 左右指针（left、right）分别初始化为矩阵左上角最小值和矩阵右下角最大值
# 若不大于中间值mid的数比k多，说明mid可能取大了，因为存在重复数字，但也可能当前mid其实就是我们想要的值，因此令right = mid
# 若不大于中间值mid的数正好k个，当前mid也可能偏大了，因为当前mid可能不在矩阵中，因此还是令right = mid
# 若不大于中间值mid的数比k少，说明mid取小了，令left = mid + 1
# 当left == right时，循环结束，返回left

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        def get_count(mid):
            i, j = n - 1, 0
            cnt = 0
            while i >= 0 and j < n:
                if matrix[i][j] <= mid:
                    cnt += i + 1
                    j += 1
                else:
                    i -= 1
            return cnt

        n = len(matrix)
        left, right = matrix[0][0], matrix[-1][-1]
        while left < right:
            mid = (left + right) // 2
            if get_count(mid) >= k:
                right = mid
            else:
                left = mid + 1
        return left