188 - 378 有序矩阵中第k小的元素

题目

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

示例:

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

返回 13。

说明: 你可以假设 k 的值永远是有效的, 1 ≤ k ≤ n2 。

解答

最方便方法，是拍扁成一维再排序

在这基础上优化，是小顶堆

双指针

https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/discuss/301357/Java-0ms-(added-Python-and-C%2B%2B)%3A-Easy-to-understand-solutions-using-Heap-and-Binary-Search

https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/discuss/85173/Share-my-thoughts-and-Clean-Java-Code

双指针关键是搜索空间。

• 如果是有序数组，可以将索引作为索引；

• 如果是无序数组，可以将值作为索引。

这题中，找到最小数和最大数的中间值，然后计算数组中小于等于mid的元素个数，拿这个和k比较。

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        lo = matrix[0][0]
        hi = matrix[len(matrix)-1][len(matrix[0])-1]+1
        while lo < hi:
            mid = (lo + hi) >> 1
            count = 0
            j = len(matrix[0])-1
            for i in range(0, len(matrix)):
                while j >= 0 and matrix[i][j] > mid:
                    j -= 1
                count += j+1
            if count < k:
                lo = mid+1
            else:
                hi = mid
        return lo

Runtime: 172 ms, faster than 96.86% of Python3 online submissions for Kth Smallest Element in a Sorted Matrix.

Memory Usage: 18.6 MB, less than 9.09% of Python3 online submissions for Kth Smallest Element in a Sorted Matrix.

这个用来统计count的方法非常巧妙啊，利用了数组都是升序的特点。

• 先用一行最大的数字比较，选择行；

• 然后在该行向前走，找到mid；

• count的值就直接通过mid的索引来求

https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/discuss/85170/O(n)-from-paper.-Yes-O(rows).

stefanPochmann的代码优化版：

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        lo = matrix[0][0]
        hi = matrix[-1][-1]
        while lo < hi:
            mid = (lo + hi) >> 1
            count = 0
            j = len(matrix[0])
            for row in matrix:
                while j >= 1 and row[j-1] > mid:
                    j -= 1
                count += j
            if count < k:
                lo = mid+1
            else:
                hi = mid
        return lo

Runtime: 180 ms, faster than 90.76% of Python3 online submissions for Kth Smallest Element in a Sorted Matrix.

Memory Usage: 18.6 MB, less than 9.09% of Python3 online submissions for Kth Smallest Element in a Sorted Matrix.

看起来更简洁了，但是更花时间😂

数学题

https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/discuss/85170/O(n)-from-paper.-Yes-O(rows).

https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/solution/on-java-by-bumblebee/

完全看不懂的数学题版本，评论区也是一片哀嚎，哭着点赞

感觉这应该是全leet最难的数学题了吧。。😂

class Solution(object):
    def kthSmallest(self, matrix, k):

        # The median-of-medians selection function.
        def pick(a, k):
            if k == 1:
                return min(a)
            groups = (a[i:i+5] for i in range(0, len(a), 5))
            medians = [sorted(group)[len(group) / 2] for group in groups]
            pivot = pick(medians, len(medians) / 2 + 1)
            smaller = [x for x in a if x < pivot]
            if k <= len(smaller):
                return pick(smaller, k)
            k -= len(smaller) + a.count(pivot)
            return pivot if k < 1 else pick([x for x in a if x > pivot], k)

        # Find the k1-th and k2th smallest entries in the submatrix.
        def biselect(index, k1, k2):

            # Provide the submatrix.
            n = len(index)
            def A(i, j):
                return matrix[index[i]][index[j]]

            # Base case.
            if n <= 2:
                nums = sorted(A(i, j) for i in range(n) for j in range(n))
                return nums[k1-1], nums[k2-1]

            # Solve the subproblem.
            index_ = index[::2] + index[n-1+n%2:]
            k1_ = (k1 + 2*n) / 4 + 1 if n % 2 else n + 1 + (k1 + 3) / 4
            k2_ = (k2 + 3) / 4
            a, b = biselect(index_, k1_, k2_)

            # Prepare ra_less, rb_more and L with saddleback search variants.
            ra_less = rb_more = 0
            L = []
            jb = n   # jb is the first where A(i, jb) is larger than b.
            ja = n   # ja is the first where A(i, ja) is larger than or equal to a.
            for i in range(n):
                while jb and A(i, jb - 1) > b:
                    jb -= 1
                while ja and A(i, ja - 1) >= a:
                    ja -= 1
                ra_less += ja
                rb_more += n - jb
                L.extend(A(i, j) for j in range(jb, ja))

            # Compute and return x and y.
            x = a if ra_less <= k1 - 1 else \
                b if k1 + rb_more - n*n <= 0 else \
                pick(L, k1 + rb_more - n*n)
            y = a if ra_less <= k2 - 1 else \
                b if k2 + rb_more - n*n <= 0 else \
                pick(L, k2 + rb_more - n*n)
            return x, y

        # Set up and run the search.
        n = len(matrix)
        start = max(k - n*n + n-1, 0)
        k -= n*n - (n - start)**2
        return biselect(range(start, min(n, start+k)), k, k)[0]

虽然是一个很酷的算法，但好像超过递归栈的极限了