1. 题目描述
2. 题目分析
- 这个题目类似于【剑指offer】-二维数组的查找-01/67
- 在此题的基础上进行一些扩展，题目要求我们找到矩阵中第K小的元素，也就是在1~15的范围中，找到第K小的数字。
- 我们对1~15进行二分，用mid来判断当前矩阵中小于等于mid的的有多少(count)，如果count小于K的话，也就是在证明当前的元素过于小，所以，需要left = mid + 1;如果count大于等于K的话，也就是证明当前的元素过于大或者正好，所以，需要right = mid。
- 这里比较困惑的一点是，怎么证明最后返回的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; }
