【LeetCode-每日一题】-378. 有序矩阵中第K小的元素

1. 题目描述

2. 题目分析

1. 这个题目类似于【剑指offer】-二维数组的查找-01/67
2. 在此题的基础上进行一些扩展，题目要求我们找到矩阵中第K小的元素，也就是在1~15的范围中，找到第K小的数字。
3. 我们对1~15进行二分，用mid来判断当前矩阵中小于等于mid的的有多少(count)，如果count小于K的话，也就是在证明当前的元素过于小，所以，需要left = mid + 1;如果count大于等于K的话，也就是证明当前的元素过于大或者正好，所以，需要right = mid。
4. 这里比较困惑的一点是，怎么证明最后返回的left一定在数组内，咱们可以这样想，首先对于第K小的元素，比如13，我们用二分找到的count只要是大于等于K的，肯定是大于等于13的，然后我们缩小mid的值，直到最后left == right，也就是最左边的边界（13），也可以理解成，在矩阵中，只有13,14是等于K的，我们需要找他最左边的值。

3. 题目代码

public int kthSmallest(int[][] matrix, int k) {
		int n = matrix.length;
		int left = matrix[0][0];
		int right = matrix[n - 1][n - 1];
		while (left < right) {
			int mid = (left + right) / 2;
			int i = n - 1;
			int j = 0;
			int num = 0;
			while (i >= 0 && j < n) {
				if (matrix[i][j] <= mid) {
					num += i + 1;
					j++;
				} else {
					i--;
				}
			}
			if (num >= k) { // 当前的数字 大于的过多 需要减少
				right = mid;
			} else {
				left = mid + 1;
			}
		}
		return left;
	}