这是一道面试题。
找到具有已排序行和列的矩阵中的第K个最小元素。第 K个 最小的元素是其中之一是否
正确？a[i, j]i + j = K
问问题
19835 次
9 回答
42
错误的。
考虑一个像这样的简单矩阵：
1 3 5
2 4 6
7 8 9
9 是最大（第 9 小）的元素。但是 9 在 A[3, 3] 和 3+3 != 9 处。（无论您使用什么索引约定，它都不正确）。
您可以在 O(k log n) 时间内通过增量合并行来解决此问题，并增加一个堆以有效地找到最小元素。
基本上，您将第一列的元素放入堆中并跟踪它们来自的行。在每一步中，您从堆中删除最小元素并从它所在的行中推送下一个元素（如果您到达行的末尾，那么您不会推送任何东西）。删除最小值和添加新元素都需要 O(log n)。在第 j 步，您删除了j第 th 个最小的元素，因此在k步骤之后，您完成了O(k log n) 操作的总成本（其中 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 次迭代后产生第 th 个最小的元素。
（如果矩阵的行多于列，则改为对列进行操作以减少运行时间。）
于 2013-03-02T21:28:23.133 回答
33
O(k log(k))解决方案。
建立一个minheap。
添加
(0,0)到堆中。然而，我们还没有找到kth最小的元素，(x,y)从堆中删除顶部元素并添加接下来的两个元素[(x+1,y)，(x,y+1)]如果它们之前没有被访问过。
我们正在O(k)对大量大小O(k)和复杂性进行操作。
于 2013-09-23T18:18:50.393 回答
7
这个问题可以使用二进制搜索和排序矩阵中的优化计数来解决。二进制搜索需要O(log(n))时间，对于每个搜索值，平均需要n次迭代才能找到小于搜索数字的数字。二分搜索的搜索空间仅限于矩阵中的最小值mat[0][0]和最大值mat[n-1][n-1]。
对于从二进制搜索中选择的每个数字，我们需要计算小于或等于该特定数字的数字。因此可以找到最小的数字。
为了更好地理解，您可以参考此视频：
于 2020-04-19T10:56:32.897 回答
1
从左上角 (0,0) 开始遍历矩阵，并使用二进制堆来存储“边界”——矩阵的已访问部分与其其余部分之间的边界。
Java中的实现：
private static class Cell implements Comparable<Cell> {
private final int x;
private final int y;
private final int value;
public Cell(int x, int y, int value) {
this.x = x;
this.y = y;
this.value = value;
}
@Override
public int compareTo(Cell that) {
return this.value - that.value;
}
}
private static int findMin(int[][] matrix, int k) {
int min = matrix[0][0];
PriorityQueue<Cell> frontier = new PriorityQueue<>();
frontier.add(new Cell(0, 0, min));
while (k > 1) {
Cell poll = frontier.remove();
if (poll.y + 1 < matrix[poll.x].length) frontier.add(new Cell(poll.x, poll.y + 1, matrix[poll.x][poll.y + 1]));
if (poll.x + 1 < matrix.length) frontier.add(new Cell(poll.x + 1, poll.y, matrix[poll.x + 1][poll.y]));
if (poll.value > min) {
min = poll.value;
k--;
}
}
return min;
}
于 2015-04-11T23:55:10.423 回答
1
上述解决方案无法处理对角线条件，不能应用于以下矩阵
int arr2[][] = { { 1, 4, 7, 11, 15 },
{ 2, 5, 8, 12, 19 },
{ 3, 6, 9, 16, 22 },
{ 10, 13, 14, 17, 24 },
{ 18, 21, 23, 26, 30 } }
k=5
返回 7 而答案是 5
于 2020-10-30T20:34:41.193 回答
0
似乎这只是使用该功能：每一行都已排序，但不使用其按列排序的功能。
于 2014-07-22T04:04:46.733 回答
0
正如人们之前提到的，最简单的方法是构建一个min heap. 这是使用 PriorityQueue 的 Java 实现：
private int kthSmallestUsingHeap(int[][] matrix, int k) {
int n = matrix.length;
// This is not necessary since this is the default Int comparator behavior
Comparator<Integer> comparator = new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
};
// building a minHeap
PriorityQueue<Integer> pq = new PriorityQueue<>(n*n, comparator);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
pq.add(matrix[i][j]);
}
}
int ans = -1;
// remove the min element k times
for (int i = 0; i < k; i++) {
ans = pq.poll();
}
return ans;
}
于 2016-09-16T20:25:30.703 回答
0
矩阵中的第 K 个最小元素：
问题可以缩小如下。
如果 k 为 20，则取 k*k 矩阵（答案肯定在哪里。）
现在您可以重复合并成对的行以构建排序数组，然后找到第 k 个最小的数字。
于 2018-04-28T18:38:20.957 回答
-1
//int arr[][] = {{1, 5, 10, 14},
// {2, 7, 12, 16},
// {4, 10, 15, 20},
// {6, 13, 19, 22}
//};
// O(k) Solution
public static int myKthElement(int arr[][], int k) {
int lRow = 1;
int lCol = 0;
int rRow = 0;
int rCol = 1;
int count = 1;
int row = 0;
int col = 0;
if (k == 1) {
return arr[row][col];
}
int n = arr.length;
if (k > n * n) {
return -1;
}
while (count < k) {
count++;
if (arr[lRow][lCol] < arr[rRow][rCol]) {
row = lRow;
col = lCol;
if (lRow < n - 1) {
lRow++;
} else {
if (lCol < n - 1) {
lCol++;
}
if (rRow < n - 1) {
lRow = rRow + 1;
}
}
} else {
row = rRow;
col = rCol;
if (rCol < n - 1) {
rCol++;
} else {
if (rRow < n - 1) {
rRow++;
}
if (lCol < n - 1) {
rCol = lCol + 1;
}
}
}
}
return arr[row][col];
}
于 2017-03-22T05:33:01.233 回答