LeetCode 378. Kth Smallest Element in a Sorted Matrix

Problem

LeetCode 378. Kth Smallest Element in a Sorted Matrix

1. 题目简述

给出一个m * n大小的矩阵，找出其第k大的数：

1. 每一行从左到右都是递增的整形数
2. 每一列从上至下都是递增的整形数

例如：

matrix = [
[ 1,  5,  9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,

return 13.

2. 算法思路

相关问题：

1. LeetCode 74. Search a 2D Matrix
2. LeetCode 240. Search a 2D Matrix II

这道题和LeetCode 240. Search a 2D Matrix II特别像，基本上是一个模子里出来的，只不过这个更麻烦一些，它并不是去找某个数那样明确的目标，而是一个比较间接的值，需要做一些小改变。

按照我们正常的思路，start和end分别是左上角和右下角，但是我们的mid并不一定在matrix中存在，我们也不能用mid + 1或者mid - 1来更新start和end。因此，我们要做的有两件事：
（1）记录全局数组中小于等于mid值的个数。

（2）需要更新的值，也就是比mid小的最大值和比mid大的最小值。

二分搜索

我们还需要注意一点，数组中可能存在重复的值，就像例子里那样，13是我们的target，但是13有两个，也就是说我们找第7小的数和第8小的数都是13，如果我们找第7个，那么当我们遍历到13的时候，我们得到的个数永远都是8，8 > 7，然后我们应该让end减小，但是小于等于13的最大的数还是13，因为我们这里有两个13，就无限循环了，start是13，end也是13.

所以，我们要注意的点就是二分搜索的循环条件，这里如果l == r，则说明当前值即为所求，不要再继续循环了。这一点一定要注意！

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        // 由于横竖都有序，所以用二分搜索继续查找也是有一定规律的，我们可以从右上或者左下进行查找，可以记一个小tips。smallLargeNumber用于记录小于middle的最大值和大于middle的最小值。
        int n = matrix.length, l = matrix[0][0], r = matrix[n - 1][n - 1];

        // 注意这里的循环结束条件，不是l <=r
        while (l < r) {
            int m = l + (r - l) / 2;
            int[] smallLargeNumber = new int[2];
            int count = countLessEqual(matrix, m, smallLargeNumber);
            if (count < k) {
                l = smallLargeNumber[1];
            } else if (count > k) {
                r = smallLargeNumber[0];
            } else {
                return smallLargeNumber[0];
            }
        }

        return l;
    }

    private int countLessEqual(int[][] matrix, int middle, int[] smallLargeNumber) {
        int n = matrix.length;
        int count = 0, row = 0, col = n - 1;

        smallLargeNumber[0] = Integer.MIN_VALUE;
        smallLargeNumber[1] = Integer.MAX_VALUE;
        while (row < n && col >= 0) {
            if (matrix[row][col] > middle) {
                smallLargeNumber[1] = Math.min(smallLargeNumber[1], matrix[row][col]);
                col--;
            } else {
                smallLargeNumber[0] = Math.max(smallLargeNumber[0], matrix[row][col]);
                count += col + 1;
                row++;
            }
        }

        return count;
    }
}