首页 文章

二进制搜索解决'Kth Smallest Element in a Sorted Matrix' . 如何确保算法的正确性，

提问于
浏览 次
1

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

这个问题有两个众所周知的解决方案 . 使用Heap / PriorityQueue和其他人使用二进制搜索 . 二进制搜索解决方案是这样的（top post）：

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 和 max 值，因此 mid 不必是数组中的值 . 但是，返回的 lo 始终是 .

为什么会这样？

binary-search whiteboard

1 回答

  • 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 最小数量的2D数组 .

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

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

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

    回复于

相关问题