即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

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

编程语言 u010150046 34℃ 0评论

在一个排序矩阵中找从小到大的第 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_queueint, pair<int, int>>, vectorint, pair<int, int>>>, greaterint, pair<int, int>>>> myqueue;
    mapint, 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;
}

转载请注明:CodingBlog » 排序矩阵里的从小到大第k个数

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情