Kth Smallest Element in a Sorted Matrix

LeetCode 378 Kth Smallest Element in a Sorted Matrix

题目描述

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.
Note that it is the kth smallest element in the sorted order, not the kth distinct element.
Example:
matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,
return 13.
Note:
You may assume k is always valid, 1 ≤ k ≤ n2.

思路：

假设我们的输入矩阵如下所示

[ A,  B,  C,  D]
[ E,  F,  G,  H]
[ I,  G,  K,  L]
[ M,  M,  O,  P]

第一小

第一小的数是哪个？左上角第一个数是最小的数，即第一小的数

第二小

第二小的数是哪个？第二小的数我们能从哪开始选择呢，因为第一小的数我们明确的知道了，以我们将第一小的数标 *

[ *,  B,  C,  D] 
[ E,  F,  G,  H]
[ I,  G,  K,  L] 
[ M,  M,  O,  P]

纵向第一个大于 * 的数是 E，横向第一个大于 * 的数是 B，所有对于全局来说，第二小的是 Min(E, B)，假设我们选择的是 E，那么第三小的数呢？

第三小

[ *,  B,  C,  D]  [ *,  F,  G,  H] [ I,  G,  K,  L]  [ M,  M,  O,  P] 此时有可能成为第三小的是 B，I，为什么 F 没有可能：因为 F 肯定大于 B，所以 在有 B 的情况下无论如何不会选择 F；而 I 与 B 的大小是无法比较的，所以只能从 B，I 中选； 这里假设我们选择的是 B，进而找第四小：

第四小

[ *,  *,  C,  D]   
[ *,  F,  G,  H]  
[ I,  G,  K,  L]   
[ M,  M,  O,  P]

现在 C，F，I 的大小均无法直接看出那个可以抛弃，所以第四小应该从他们三个中选则。

总结

通过上面三步我们可以总结出一个规律，获取当前步的最小值时，能够参加候选的数需要满足以下条件： 该数的左边和上边都没有数 如果一个数 X 的左边或者右边都还有数的话，那么对于当前步来说，一定有左边或者上边的值小于 X 的，所以选取当前步的最小值的时候一定轮不到 X