LeetCode刷题——有序矩阵中第 K 小的元素#378#Medium

有序矩阵中第 K 小的元素的思路探讨与源码
    有序矩阵中第 K 小的元素的题目如下图，该题属于数组类和排序类型的题目，主要考察对于排序方法的使用和数组结构的理解。本文的题目作者想到2种方法，分别是归并排序方法和二分查找方法，其中二分查找方法使用Java进行编写，而归并排序方法使用Python进行编写，当然这可能不是最优的解法，还希望各位大佬给出更快的算法。

    本人认为该题目可以使用二分查找方法的思路进行解决，首先计算矩阵的长度，并把矩阵的左上角原元素和右下角元素赋值给两个搜索标记，然后开始进行搜索，将元素值求差值后进行二进制右0移1位的操作并和左边的下标求和并记录，调用二分搜索函数进行搜索。在二分搜索函数的内部，主要是对传入的值进行循环搜索遍历，如果矩阵当前元素值要小于等于传入值，那么就将下标移动并进行值的记录并且继续搜索，直到最终返回判断标记值是否大于等于目标值的结果。调用二分搜索函数以后，判断结果是否为真，如果是真就将记录下标赋值给右边下标，否则把记录下标加1后赋值给左下标，直到循环结束并返回最终的坐下标的结果。那么按照这个思路我们的Java代码如下：

#喷火龙与水箭龟
class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int numLen = matrix.length;
        int a = matrix[0][0];
        int b = matrix[numLen - 1][numLen - 1];
        while (a < b) {
            int ind = a + ((b - a) >> 1);
            if (examSearch(matrix, ind, k, numLen)) {
                b = ind;
            } else {
                a = ind + 1;
            }
        }
        return a;
    }
    public boolean examSearch(int[][] matrix, int ind, int k, int numLen) {
        int ir = numLen - 1;
        int jr = 0;
        int ez = 0;
        while (ir >= 0 && jr < numLen) {
            if (matrix[ir][jr] <= ind) {
                ez = ez + ir + 1;
                jr = jr + 1;
            } else {
                ir = ir - 1;
            }
        }
        return ez >= 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
28
29
30
31

    显然，我们的二分查找方法的效果还不错，还可以使用归并排序的方法解决。首先计算矩阵的长度，然后初始化一个带有矩阵元素的列表，将列表转为堆进行操作，初始化下标值，然后开始搜索，把堆的元素按循环进行抛出，判断元素值是否到矩阵的长度了，如果没有则将矩阵的下一个元素和对应的列表结果放入堆，直到遍历结束并返回最终的第一个值，即有序矩阵第K小的元素结果并返回。所以按照这个思路就可以解决，下面是Python代码：

#喷火龙与水箭龟
class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        numLen = len(matrix)
        arr = [(matrix[ir][0], ir, 0) for ir in range(numLen)]
        heapq.heapify(arr)
        ind = 0
        for jr in range(k - 1):
            num, x, y = heapq.heappop(arr)
            if(y != numLen - 1):
                heapq.heappush(arr, (matrix[x][y + 1], x, y + 1))
        return heapq.heappop(arr)[0]
1
2
3
4
5
6
7
8
9
10
11
12

    从结果来说Java版本二分查找方法的效率不错，而Python版本的归并排序方法的速度比较一般，但应该是有更多的方法可以进一步提速的，希望朋友们能够多多指教，非常感谢。