leetcode——378. 有序矩阵中第 K 小的元素_leetcode378完整代码

思路1

1. 将二维数组转为一位数组进行排序
2. 但是这样没有利用到 每行和每列元素均按升序排序

代码1

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        vector<int> ans;
        for(int i=0;i<matrix.size();i++)
            for(int j=0;j<matrix[0].size();j++)
                ans.emplace_back(matrix[i][j]);
        sort(ans.begin(),ans.end());
        return ans[k-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11

思路2

1. 使用优先队列，结构为<val,x,y>
2. 按照每行有序的特点，每次压入栈顶的右元素，保证其为较小的值；
   （如果其不是当前元素的下一个值，那么就会是下一行的头元素）

代码2

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        struct point {
            int val, x, y;
            point(int val, int x, int y) : val(val), x(x), y(y) {}
            bool operator> (const point& a) const { return this->val > a.val; }
        };
        
        //创建优先队列 存入每行头地址
        priority_queue<point, vector<point>, greater<point>> 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++) {
            point 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;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26