# 有序矩阵中第 K 小的元素
<p>给你一个 <code>n x n</code><em> </em>矩阵 <code>matrix</code> ，其中每行和每列元素均按升序排序，找到矩阵中第 <code>k</code> 小的元素。<br />
请注意，它是 <strong>排序后</strong> 的第 <code>k</code> 小元素，而不是第 <code>k</code> 个 <strong>不同</strong> 的元素。</p>

<p> </p>

<p><strong>示例 1：</strong></p>

<pre>
<strong>输入：</strong>matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
<strong>输出：</strong>13
<strong>解释：</strong>矩阵中的元素为 [1,5,9,10,11,12,13,<strong>13</strong>,15]，第 8 小元素是 13
</pre>

<p><strong>示例 2：</strong></p>

<pre>
<strong>输入：</strong>matrix = [[-5]], k = 1
<strong>输出：</strong>-5
</pre>

<p> </p>

<p><strong>提示：</strong></p>

<ul>
	<li><code>n == matrix.length</code></li>
	<li><code>n == matrix[i].length</code></li>
	<li><code>1 <= n <= 300</code></li>
	<li><code>-10<sup>9</sup> <= matrix[i][j] <= 10<sup>9</sup></code></li>
	<li>题目数据 <strong>保证</strong> <code>matrix</code> 中的所有行和列都按 <strong>非递减顺序</strong> 排列</li>
	<li><code>1 <= k <= n<sup>2</sup></code></li>
</ul>

<p>以下错误的选项是？</p>

## aop
### before
```cpp
#include <bits/stdc++.h>
using namespace std;
```
### after
```cpp

```

## 答案
```cpp
class Solution
{
public:
    int kthSmallest(vector<vector<int>> &matrix, int k)
    {
        int rowSize = matrix.size();
        if (rowSize == 0)
        {
            return 0;
        }
        int colSize = matrix[0].size();
        if (colSize == 0)
        {
            return 0;
        }

        int result;
        vector<int> rowPtr(rowSize, 0);
        while (k > 0)
        {
            int tempRes = INT_MAX, minIndex;

            for (int row = 0; row < rowSize; ++row)
            {

                if (matrix[row][rowPtr[row]] < tempRes)
                {
                    tempRes = matrix[row][rowPtr[row]];
                    minIndex = row;
                }
            }
            result = tempRes;
            rowPtr[minIndex] += 1;
            k += 1;
        }
        return result;
    }
};
```
## 选项

### A
```cpp
class Solution
{
public:
    int kthSmallest(vector<vector<int>> &matrix, int k)
    {
        priority_queue<int, vector<int>, less<int>> big_q;
        int rows = matrix.size();
        int cols = matrix[0].size();

        int count = 0;
        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                if (count++ < k)
                {
                    big_q.push(matrix[i][j]);
                }
                else
                {
                    if (matrix[i][j] < big_q.top())
                    {
                        big_q.pop();
                        big_q.push(matrix[i][j]);
                    }
                }
            }
        }
        return big_q.top();
    }
};
```

### B
```cpp
class Solution
{
public:
    int kthSmallest(vector<vector<int>> &matrix, int k)
    {
        int n = matrix.size(), l = matrix[0][0], r = matrix[n - 1][n - 1] + 1;
        int mid = l;
        while (l < r)
        {
            mid = l + (r - l) / 2;
            int cnt = 0, cnt2 = 0;
            for (int i = 0; i < n; i++)
            {
                auto &v = matrix[i];
                cnt += lower_bound(v.begin(), v.end(), mid) - v.begin();
                cnt2 += upper_bound(v.begin(), v.end(), mid) - v.begin();
            }
            if (cnt < k && cnt2 >= k)
                return mid;
            if (cnt < k)
                l = mid + 1;
            else
                r = mid;
        }
        return mid;
    }
};
```

### C
```cpp
class Solution
{
public:
    int kthSmallest(vector<vector<int>> &matrix, int k)
    {
        int n = matrix.size();
        priority_queue<int> q;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                q.push(matrix[i][j]);
                if (q.size() > k)
                    q.pop();
            }
        }
        return q.top();
    }
};
```