LeetCode 378 Kth Smallest Element in a Sorted Matrix

概述

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