LeetCode 378 Kth Smallest Element in a Sorted Matrix

Tag: 数组类题目 LeetCode Posted on 2022-03-08 19:30:03 Edited on 2022-03-08 20:28:33 Views: 157

概述

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

未经允许,禁止转载,本文源站链接:https://iamazing.cn/