排序矩阵中的从小到大第k个数

本文主要是介绍排序矩阵中的从小到大第k个数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在一个排序矩阵中找从小到大的第 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;
}

这篇关于排序矩阵中的从小到大第k个数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---