题目
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.
题意
给定一个n*n介矩阵，该矩阵每一行每一列都是排序的。求该矩阵中第k小的数字
题解
该题可以使用二分查找的方法来求解。说是二分查找，其实准确的说是利用二分查找的思想。因为该矩阵行列递增排序，所以我们知道左上角为最小值，右下角为最大值。所以取left=最小值，right=最大值，mid=left+(right-left)/2，然后再求出小于等于mid的元素个数，记为Count,如果Count<k，则left=mid+1,否则right=mid；不断寻找直到left<right不满足，返回lef或right即为所求元素。
这里关于求出小于等于mid的元素个数，可以利用该矩阵的特性。从左下角开始找，当左小角元素<=mid时，该列都小于mid，则有res +=line+1,并向右移动一列，若大于mid，则向上走row–;
代码
func kthSmallest(matrix [][]int, k int) int {
n := len(matrix)
if n == 0 {
return -1
}
left := matrix[0][0]
right := matrix[n-1][n-1]
count:=0
for left<right{
mid := left + (right-left)/2
count = lessMidCount(matrix,mid)
if count<k{
left = mid+1
}else{
right = mid
}
}
return left
}
func lessMidCount(matrix [][]int,mid int)int{
n := len(matrix)
row := n-1
line := 0
count := 0
for row>=0&&line<n{
if matrix[row][line] <= mid{
count += row+1
line++
}else{
row--
}
}
return count
}
总结
今天状态总感觉不太好，这道题浪费了我好多时间。一开始想了一种根据k的位置去求，先确定他在对角线上的第几个元素（左上到右下），然后再根据k-其他层的个数，求出他在最边行和最边列k的相对位置，比较大小，简直傻逼。
然后上网搜了这种做法，简单的说并不难理解，二分搜索，根据k和小于mid的值进行划分，在利用矩阵的特性提高寻找小于mid个数的效率。
但是问题在于，count=k应该如何操作，k等于count说明小于mid的个数刚好为k个，count小于k则需要向右边靠拢，大于k则需要向左边靠拢，等于k呢？这里是做跟>k相同的操作，并且大于k时right=mid，但是小于k是left=mid+1，？？？这里为什么一个+1，一个不+1，如何做区分的？
很烦。。
