LeetCode 378 Kth Smallest Element in a Sorted Matrix

    
        标签：
        
            数组类题目
        
            LeetCode
        
    发布于：2022-03-08 19:30:03
    编辑于：2022-03-08 20:28:33
    浏览量：758

概述

https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/

空间复杂度要求优于 O(n^2)。

暴力法

将各个有序的列合并到一整个列，空间复杂度 O(n)，用来记录每一列搞到哪里了。

时间复杂度 O(kn)。

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int c = 0;
        vector<int> indices(matrix.size(), 0);
        int minr;
        while (c < k) {
            int minv = INT_MAX;
            for (int r = 0; r < matrix.size(); r ++) {
                if (indices[r] < matrix.size() && matrix[r][indices[r]] < minv) {
                    minv = matrix[r][indices[r]];
                    minr = r;
                }
            }
            indices[minr] ++;
            c ++;
        }
        return matrix[minr][indices[minr] - 1];
    }
};

二分搜索法

https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/discuss/85182/my-solution-using-binary-search-in-c/90001

我们要找的无非就是一个值，该值存在于矩阵中，且小于该值的数值个数为 k，那我们自然可以二分搜索该数。

二分搜索复杂度为 O(log(n^2))，每次要统计小于该值的数值个数，用二分搜索来搜索每行来进行寻找，复杂度 O(nlogn)，因此总的时间复杂度为 O(2n(logn)^2)

class Solution
{
public:
    int kthSmallest(vector<vector<int>>& matrix, int k)
    {
        int n = matrix.size();
        int le = matrix[0][0], ri = matrix[n - 1][n - 1];
        int mid = 0;
        while (le < ri)
        {
            mid = le + (ri-le)/2;
            int num = 0;
            for (int i = 0; i < n; i++)
            {
                int pos = upper_bound(matrix[i].begin(), matrix[i].end(), mid) - matrix[i].begin();
                num += pos;
            }
            if (num < k)
            {
                le = mid + 1;
            }
            else
            {
                ri = mid;
            }
        }
        return le;
    }
};

Links: leetcode-378-kth-smallest-element-in-a-sorted-matrix