Leetcode 378. 有序矩阵中第 K 小的元素（DAY 149） ---- LeetCode 精选 TOP 面试题

悠悠 2022-09-06 15:26 141阅读 0赞

### 文章目录 ###

*   *  原题题目
     *  代码实现（首刷看解 DAY 149 优先队列）

--------------------

## 原题题目 ##

--------------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70]

--------------------

## 代码实现（首刷看解 DAY 149 优先队列） ##

--------------------

class Solution { 
    public:
        int kthSmallest(vector<vector<int>>& matrix, int k) { 
            struct elem { 
                int val, x, y;
                elem(int val, int x, int y) : val(val), x(x), y(y) { }
                bool operator> (const elem& a) const {  return this->val > a.val; }
            };
            priority_queue<elem,vector<elem>,greater<elem>> que;
            int n = matrix.size();
            for (int i = 0; i < n; i++) 
                que.emplace(matrix[i][0], i, 0);
            for (int i = 0; i < k - 1; i++) { 
                elem now = que.top();
                que.pop();
                if (now.y != n - 1) { 
                    que.emplace(matrix[now.x][now.y + 1], now.x, now.y + 1);
                }
            }
            return que.top().val;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70]: /images/20220829/dbd33e0cbb8546a38b9f211c0c8ebbee.png