当前位置：网站首页>LeetCode-378. 有序矩阵中第K小的元素

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

2020-11-09 22:18:00 【yew0】

题目下图所示：

　　题目大意是给定一个n*n的矩阵，每行从左到右和每列从上到下是递增的序列，找出矩阵中第k小的数。

方案一：

　　最简单的方式是将矩阵中的数都放在一个序列中，重新由小到大排序，然后输出第k个数，暴力解法。

　　实现代码：

class Solution {
public:
    int kthSmallest1(vector<vector<int>>& matrix, int k) {
        int m[200001];
        int nNum = 0;
        for(int i=0; i<matrix.size(); i++) {
            for(int j=0; j<matrix[i].size(); j++) {
                m[nNum++] = matrix[i][j];
            }
        }
        sort(m, m+nNum);
        return m[k-1];
    }
};

方案二：

　　因为矩阵每行和每列都是有序的，可以使用二分查找来进行；取矩阵中前后两个数值的平均值来做查找，平均值跟矩阵中的数做对比，从上到下，从右到左，假如平均值大于等于矩阵的某一行的第N个值那么，那行就有N个数小于平均值，下一行就从第N个数开始比较，因为上一行的第N+1个数值比平均值大，下一行的肯定比平均值大，所以可以从第N个数开始；然后得到平均值比矩阵中的数大于等于的个数S，如果S大于等于K，最右边的数值R=平均值，否则，最左边的数值L=平均值+1；按照上述查找S的个数，然后和K比较，直到R不再大于L，输出L。

下面为部分流程的图解：

例子：[[1,3,5],[2,3,6],[4,5,7]]，找第K=4个小的数

L：最左边的数值

R：最右边的数值

M：L和R的平均值

S：矩阵中小于M的个数

X：当前行最右边的位置

Y：当前行位置

图一：初始化数据，L=1，R=7，计算出M=4

图二到六：进行平均值M与矩阵的数值做对比，图二的matrix[Y][X]=5比M=4大，X=X-1，比较前一位的数值；图三matrix[Y][X]=3比M=4小，则S加上第0行的个数，Y=Y+1，比较下一行；图四matrix[Y][X]=3比M=4小，则S加上第1行的个数，Y=Y+1，比较下一行；图五matrix[Y][X]=5比M=4大，X=X-1，比较前一位的数值；图六matrix[Y][X]=4与M=4相等，则S加上第1行的个数；完成矩阵的比较，得到最终的S。

图七：S=5比K=4大，所以R=M=4

图八：计算出M=2，进行下一轮的比较，比较流程跟图二和六的做法一致，直到L大于等于R。

实现代码：

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        int nm = n - 1;
        int nLeft = matrix[0][0];
        int nRight = matrix[nm][nm];
        while(nLeft < nRight) {
            int nMid = (nLeft + nRight) / 2.0;
            int nMaxx = 0;
            int nMaxy = nm;
            int nSize = 0;
            while(nMaxy >= 0 && nMaxx < n) {
                if(matrix[nMaxx][nMaxy] <= nMid) {
                    nSize += (nMaxy + 1);
                    nMaxx++;
                }
                else {
                    nMaxy--;
                }
            }
            if(nSize >= k) {
                nRight = nMid;
            }
            else {
                nLeft = nMid + 1;
            }
        }
        return nLeft;
    }
};