在一个排序矩阵中找从小到大的第 k 个整数。 排序矩阵的定义为：每一行递增，每一列也递增。 样例 给出 k = 4 和一个排序矩阵：
[ [1 ,5 ,7], [3 ,7 ,8], [4 ,8 ,9], ]返回 5；
本题目最坏的情况下是O（n^2）的时间复杂度，所以可以在此基础上利用一个优先队列，一个map，不断的将数组中的元素和相应的坐标存进队列内，并去除队列中的对头元素判断该元素所对应的坐标是否在map中存在，直到第K个元素；
int kthSmallest(vector<vector<int> > &matrix, int k) { if (matrix.size() == 0 || k <= 0)return 0; int m = matrix.size(), n = matrix[0].size(); if (k > m * n)return 0; priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> myqueue; map<pair<int, int>, bool> visited; myqueue.push({ matrix[0][0], { 0, 0 } }); visited[{0, 0}] = true; while (k--){ auto cur = myqueue.top(); if (k == 0)return cur.first; myqueue.pop(); int row = cur.second.first, col = cur.second.second; if (row + 1 < m && visited[{row + 1, col}] == false){ myqueue.push({ matrix[row + 1][col], { row + 1, col } }); visited[{row + 1, col}] = true; } if (col + 1 < n && visited[{row, col + 1}] == false){ myqueue.push({ matrix[row][col + 1], { row, col + 1 } }); visited[{row, col + 1}] = true; } } return 0; }