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