【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;
	}