leetcode Kth Smallest Element in a Sorted Matrix

leetcode Kth Smallest Element in a Sorted Matrix

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:
1
2
3
4
5
6
7
8
matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

return 13.
Note: You may assume k is always valid, 1 ≤ k ≤ n2.

题目地址：leetcode Kth Smallest Element in a Sorted Matrix

题意：给定一个每一行每一列都排好序的矩阵，求其中第k大的元素

思路：

先想到的就是用堆。直接维护一个大小为k的堆，全部读入一遍，这样平均和最坏情况都为O(n^2 * logk) 很暴力，没有利用有序的特点。

因为每一行和每一列都是有序的了，因此维护一个最小堆，每次取出堆顶的元素，然后把它下方的元素放进堆(如果是第一行，还要把它右边的元素放入，这样不会重复。)

这样做K次后堆顶元素就是第K大的了。这样复杂度为多少呢？O(KlogK) 然而K最坏情况是n^2..... 因此，这个方法也一般。

PS: 本来写k - - > 0 的，想到以前知乎上看到的 C语言有啥奇技淫巧， - - >是趋向于，哈哈哈~ 一本正经的胡说八道

struct Node {
	int val, i, j;
	Node(int i, int j, int val) :i(i), j(j), val(val) {}
	bool operator < (const Node & x)const {
		return val > x.val;
	}
};

class Solution {
public:
	int kthSmallest(vector<vector<int>>& matrix, int k) {
		priority_queue<Node> q;
		int n = matrix.size();
		q.push(Node(0, 0, matrix[0][0]));
		while (--k > 0) {
			Node  x = q.top(); q.pop();
			if (x.i == 0 && x.j + 1 < n) q.push(Node(x.i, x.j + 1, matrix[x.i][x.j + 1]));
			if (x.i + 1 < n) q.push(Node(x.i + 1, x.j, matrix[x.i + 1][x.j]));
		}
		return q.top().val;
	}
};

我觉得用二分做最好，这个方法只要求行有序，和列有木有序并没有关系。（或者列有序，行有序无序都没关系）

设L = min(matrix) R= max(matrix) , mid =( L + R ) / 2 ，mid为我们猜测的答案。

然后对于每一行，找它在该行中第几大（也是二分，找上界），累加和K比较。

值得注意的是枚举答案应该用下界，因为猜想的解不一定在数组中，不断的收缩直到找到在数组中的元素为止。

查找一行需要log(n) ，有n行所以nlog(n)，最坏下需要查找log(X)次（X= int最大值的时候logX仅仅才为32），X为最大最小数差值。所以总复杂度为O(nlogn * logX)

PS：其实是我一开始看成就行有序→_→，然后就直接二分了

C++

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

Java

public class Solution {
    public int kthSmallest(int[][] matrix, int k) {
		int n = matrix.length;
		int L = matrix[0][0], R = matrix[n - 1][n - 1];
		while (L < R) {
			int mid = L + ((R - L) >> 1);
			int temp = 0;
			for (int i = 0; i < n; i++) temp += binary_search(matrix[i], n, mid);
			if (temp < k) L = mid + 1;
			else R = mid;
		}
		return L;
	}
	
	private int binary_search(int[] row,int R,int x){
	    int L = 0;
	    while (L < R){
	        int mid = (L + R) >> 1;
	        if(row[mid] <= x) L = mid + 1;
	        else R = mid;
	    }
	    return L;
	}
}

Python

class Solution(object):
    def kthSmallest(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        n = len(matrix)
        L, R = matrix[0][0], matrix[n - 1][n - 1]
        while L < R:
            mid = L + ((R - L) >> 1)
            temp = sum([self.binary_search(y,mid,n) for y in matrix])
            if temp < k:  L = mid + 1
            else:  R = mid
        return L

    def binary_search(self, row, x, n):
        L, R = 0, n
        while L < R:
            mid = (L + R) >> 1
            if row[mid] <= x: L = mid + 1
            else:  R = mid
        return L

上述的解法并没有利用到列有序的性质。

而下面的解法利用了列有序的性质，并将复杂度降到了O(nlogX) 其中X = max - min

我们仍采用猜测法，设L = min(matrix) R= max(matrix) , mid =( L + R ) / 2 ，mid为我们猜测的答案。

对于mid，我们不必再所有的行或列种执行二分查找，我们可以从左下角出发，若matrix[i][j] <= mid，则下一次查询在右边（j++），并且，该列的所有元素均比mid小，因此可以cnt += (i+1)

对于matrix[i][j] > mid，则 i - - 。过程类似于240. Search a 2D Matrix II (题解在最下方)

C++

class Solution {
public:
	int kthSmallest(vector<vector<int>>& matrix, int k) {
		int n = matrix.size();
		int L = matrix[0][0], R = matrix[n - 1][n - 1];
		while (L < R) {
			int mid = L + ((R - L) >> 1);
			int temp = search_lower_than_mid(matrix, mid, n);
			if (temp < k) L = mid + 1;
			else R = mid;
		}
		return L;
	}
	int search_lower_than_mid(const vector<vector<int>>& matrix, int x, const int n) {
		int i = n - 1, j = 0, cnt = 0;
		while (i >= 0 && j < n) {
			if (matrix[i][j] <= x) {
				j++;
				cnt += i + 1;
			}
			else i--;
		}
		return cnt;
	}
};

Java

public class Solution {
    public int kthSmallest(int[][] matrix, int k) {
		int n = matrix.length;
		int L = matrix[0][0], R = matrix[n - 1][n - 1];
		while (L < R) {
			int mid = L + ((R - L) >> 1);
			int temp = search_lower_than_mid(matrix, n, mid);
			if (temp < k) L = mid + 1;
			else R = mid;
		}
		return L;
	}
	
	private int search_lower_than_mid(int[][] matrix,int n,int x) {
		int i = n - 1, j = 0, cnt = 0;
		while (i >= 0 && j < n) {
			if (matrix[i][j] <= x) {
				j++;
				cnt += i + 1;
			}
			else i--;
		}
		return cnt;
	}
}

Python

class Solution(object):
    def kthSmallest(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        n = len(matrix)
        L, R = matrix[0][0], matrix[n - 1][n - 1]
        while L < R:
            mid = L + ((R - L) >> 1)
            temp = self.search_lower_than_mid(matrix, n, mid)
            if temp < k:
                L = mid + 1
            else:
                R = mid
        return L

    def search_lower_than_mid(self, matrix, n, x):
        i, j = n - 1, 0
        cnt = 0
        while i >= 0 and j < n:
            if matrix[i][j] <= x:
                j += 1
                cnt += i + 1
            else:
                i -= 1
        return cnt

当然也可以从右上角到左下角，以Python为例，相应的函数改成如下即可：

def search_lower_than_mid(self, matrix, n, x):
    i, j = 0, n - 1
    cnt = 0
    while i < n and j >= 0:
        if matrix[i][j] <= x:
            i += 1
            cnt += j + 1
        else:
            j -= 1
    return cnt

本题是leetcode 378 Kth Smallest Element in a Sorted Matrix题解

更多题解可以查看：https://www.hrwhisper.me/leetcode-algorithm-solution/