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:

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

return 13.

解题思路

1. 使用暴力解法，直接将所有元素集中到一个数组中，然后排序（快速），最后返回第k个数；
2. 维护一个最小堆

代码

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

/*
创建一个有k个元素的数组，先用矩阵的前k个元素填满，需按照升序排序 
从第k+1个开始遍历矩阵
 
*/

class Solution {
public:
    int kthSmallest(vector<vector<int> >& matrix, int k) {
		int n = matrix.size();
		int c = 0;
		vector<int> target; 
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				target.push_back(matrix[i][j]);	
			}
		}
		
		sort(target.begin(), target.end());
		return target[k-1];
    }
    
    
};

int main(){
	int x[3][3] = {
		{
			1,5,9
		},
		{
			10,11,13
		},
		{
			12,13,15
		}
	};
	vector<vector<int> > matrix;
	int a = 1;
	for(int i=0;i<3;i++) {
		vector<int> t;
		for(int j=0;j<3;j++) {
			t.push_back(x[i][j]);
		}
		matrix.push_back(t);
	}
	Solution s;
	int kth = s.kthSmallest(matrix, 8);
	cout<<kth;
}