Leetcode 378. 有序矩阵中第 K 小的元素

题目描述：

Leetcode

解题思路：

二分法

如上图所示 ，因为该矩阵行列都是从小到大排列的，我们可以知道该矩阵的最大值15和最小值1，因此对于任意一个mid(min<mid<max)都可以知道矩阵中大于小于该元素值的个数。例如，mid=8,我们可以知道矩阵中小于8的个数为2。用类似的思想就可以解出该题。

以上图矩阵为例，求第k=8小对应的元素，实现过程如下：

step 1:left=1,right=15,mid=8 count=2<k=8说明此时的范围太小，应该扩大范围

step 2:left=mid+1=9,right=15,mid=12 count=6<k=8

step3:left=mid+1=13,right=15,mid=14,count=8=k=8说明此时第k小在该范围内，即矩阵中小于等于13的数是8个但是我们还不能确定矩阵中第8小是谁

step4:left=13,right=mid=14,mid=13,count=8=k=8

step5:left=13,right=13,收敛

如何计算矩阵内小于等于mid的个数参考：

思想类似于

240.搜索二维矩阵

如图，从左到右，从上到下计算小于等于mid的数目

#include<iostream>
#include<vector>
using namespace std;
 class Solution {
public:
    int CalculateCount(vector<vector<int>>&matrix,int target){
        int count = 0;
        int row = matrix.size(), col = matrix[0].size();
        int i = 0, j = col - 1;
        while(i<row&&j>=0)
        {
            if(target>=matrix[i][j])
            {
                 count = count + j+1;
                 i++;
            } 
            else{
                j--;
            }

        }
        return count;
    }
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int m,n;
        m = n = matrix.size();
        int low = matrix[0][0], high = matrix[m - 1][n - 1], mid = 0;
        int count = 0;
        if(n==1)
            return matrix[0][k - 1];
        while(low!=high){
            mid = (low + high) / 2;
            cout << mid << " ";
            count = CalculateCount(matrix, mid);
            cout << count<<endl;
            if(count<k)
                low = mid + 1;//矩阵中大于Mid的数有count,count<k说明Mid的范围太小了，应该扩大
            else
                high = mid;//count>=k说明第k小的数包好在[low,mid]的范围（范围过大），但是具体在哪还不确定需要进一步细化

        }
        return low;
    }
};
int main()
{
    int m = 3, n = 3;
    int target = 5;
    vector<vector<int>> matrix(m, vector<int>(n));
    vector<int> v;
    int i, j;
    for (i = 0; i < m;i++)
        for (j = 0; j < n;j++)
            cin >> matrix[i][j];
    Solution sl;
    int value = sl.kthSmallest(matrix, 8);
    cout << value<<endl;
    /*
    for (i = 0; i < m;i++)
    {
        for (j = 0; j < n;j++)
            cout << matrix[i][j] << " ";
        cout << endl;
    }*/
        return 0;
}