1

我指的是 leetcode 问题：Kth Smallest Element in a Sorted Matrix

该问题有两种众所周知的解决方案。一种使用 Heap/PriorityQueue，另一种使用 Binary Search。二进制搜索解决方案是这样的（顶帖）：

public class Solution {
public int kthSmallest(int[][] matrix, int k) {
    int lo = matrix[0][0], hi = matrix[matrix.length - 1][matrix[0].length - 1] + 1;//[lo, hi)
    while(lo < hi) {
        int mid = lo + (hi - lo) / 2;
        int count = 0,  j = matrix[0].length - 1;
        for(int i = 0; i < matrix.length; i++) {
            while(j >= 0 && matrix[i][j] > mid) j--;
            count += (j + 1);
        }
        if(count < k) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}
}

虽然我了解这是如何工作的，但我无法解决一个问题。我们如何确定返回lo的总是在矩阵中？

由于搜索空间是数组的值，因此不需要是数组min中的值。但是，返回的总是。maxmidlo

为什么会这样？

4

2 回答 2

0

因为我们正在使用二进制搜索找到 lower_bound 并且不能有任何数字小于数组中可能是第 k 个最小元素的 number(lo)。

于 2020-01-21T16:46:15.610 回答
0

为了论证，我们可以将 的计算count移到一个单独的函数中，如下所示：

bool valid(int mid, int[][] matrix, int k) {
    int count = 0, m = matrix.length;
    for (int i = 0; i < m; i++) {
        int j = 0;
        while (j < m && matrix[i][j] <= mid) j++;
        count += j;
    }
    return (count < k);
}

该谓词将与您指定的操作完全相同。在这里，循环不变量是，范围[lo, hi]总是包含kth二维数组的最小数字。

换句话说，lo <= solution <= hi

现在，当循环终止时，很明显lo >= hi

合并这两个属性，我们得到，lo = solution = hi因为solution是数组的成员，所以可以说，lo在循环终止后总是在数组中，并且会正确地指向kth最小的元素。

于 2018-03-17T19:01:27.153 回答