共有3个答案
这个问题可以通过二进制搜索和排序矩阵中的优化计数来解决。二进制搜索需要O（log（n））时间，对于每个搜索值，平均需要n次迭代才能找到小于搜索数的数字。二进制搜索的搜索空间限于矩阵中mat[0][0]处的最小值和mat[n-1][n-1]处的最大值。
为了更好的理解，你可以参考这个视频：
https://www.youtube.com/watch?v=G5wLN4UweAM
O（k log（k））解。
>
建造一个垃圾堆。
将（0,0）添加到堆中。虽然我们还没有找到kth最小的元素，但是从堆中移除顶部的元素（x，y），然后添加接下来的两个元素[（x 1，y）和（x，y 1）]，如果它们以前没有被访问过的话。
我们在大小O（k）的堆上执行O（k）操作，从而增加了复杂性。
假的。
考虑像这样的简单矩阵：
1 3 5
2 4 6
7 8 9
9是最大的（第九小的）元素。但是9在A[3,3]，并且3 3！=9。（无论您使用什么索引约定，它都不可能是真的）。
通过增量合并行，加上堆以高效地找到最小元素，可以在O（k logn）时间内解决这个问题。
基本上，将第一列的元素放入堆中，并跟踪它们来自的行。在每一步中，从堆中移除最小元素，并从其所在的行中推送下一个元素（如果到达行的末尾，则不推送任何内容）。删除最小值和添加新元素都会消耗O（logn）。在第j步中，删除jth最小的元素，因此在k步之后，您将完成O（k logn）操作的总成本（其中n是矩阵中的行数）。
对于上面的矩阵，您最初从堆中的1,2,7开始。您删除1并添加3（因为第一行是1 3 5）以获得2,3,7。您删除2并添加4以获得3,4,7。删除3并添加5以获得4,5,7。删除4并添加6以获得5,6,7。请注意，我们正在以全局排序的顺序删除元素。您可以看到，继续这个过程将在k次迭代后产生第k个最小的元素。
（如果矩阵的行多于列，则对列进行操作以减少运行时间。）
-
所以我正在研究一个Leetcode问题，我的代码在某些情况下有效，但在某些情况下失败。 问题是： 给定一个矩阵，其中每个行和列都按升序排序，找出矩阵中第k个最小的元素。 请注意，它是排序顺序中的第k个最小元素，而不是第k个独立元素。 例子： 返回： 13 我的方法是使用minHeap，即使它声明数组已经排序，我仍然需要确保我已经将它从最小值排序到最大值。 这是我的代码： 以下是我的意见： 以下是输
-
我的问题是受到这个特殊的SO评论的启发，这个评论没有得到回答（我自己也面临这个问题）： 我试图找到排序矩阵中第K个最小的元素： 给定一个nxn矩阵，其中每个行和列都按升序排序，返回矩阵中第k个最小的元素 请注意，它是排序顺序中的第k个最小元素，而不是第k个独立元素 输入：矩阵=[[1,5,9]，[10,11,13]，[12,13,15]，[12,13,15]，k=8 输出：13 说明：矩阵中的元素
-
这是一个面试问题。 在排序的行（但不是排序的列）和行之间没有关系的矩阵中查找第k个最小元素。（第一行和第n行之间没有关系——我们只知道每一行都是按升序排列的） 输入示例如下： 这种情况下的结果是 因为20是这个矩阵中第五小的元素。 我首先想到将所有元素添加到minHeap中，然后轮询元素，同时每次迭代从k中减去一个，直到我们得到答案。我还考虑为O（m*n）解决方案实现快速选择，尽管这些解决方案并没
-
我知道以前有人问过这个问题，但这个问题是关于我的具体代码。我试图做一个psuedo-QuickSelect算法，将k与排序矩阵子区间的中点进行比较。 我一直收到一个超时错误。 以下是矩阵： 下面是我的代码： 我将元组传递给，其中包含区间的endpoint的。因此，如果我想搜索整个矩阵，我会传递和。将查看子区间，根据endpoint的行号确定中点，计算小于中点的元素数量，将其与进行比较。如果小于小于
-
这可能是微软的面试问题。 从排序的数组中找出第k个最小的元素（忽略重复项） [编辑]：数组可能包含重复项（未指定）。 想了很多次，但仍然质疑自己：还有更好的解决方案吗？ 取最大堆 时间复杂度：O（NlogK） 空间复杂度：O（K） 这些元素可能是重复的。所以，通过与以前的元素进行比较来检查是否有唯一的元素 还可以使用改进版的快速排序分区算法。但它可能会导致最坏的情况，因为数组已经排序<这里出现了两
-
我最近接受了一家社交媒体公司的面试，在那里我被问到了以下问题。 有k个长度为m的未排序数组。目标是在给定a 我提出了两个可能的解决方案: null 对于使用quickselect查找第b个最小元素的第一步，平均时间总共从O(km)到O(km*log(m))。第二步时间复杂度为O（km）。最后一步是在C中的第a和第b个最小元素之间寻找元素，取O（（b-a）log(kb))。因此，total在时间上需