378. Kth Smallest Element in a Sorted Matrix

使用堆（只应用了行递增而没有用列递增）

对于矩阵

借助归并排序思想，把每一行视为一个递增序列，如果归并的话，就是把每一行归并序列合并为一个递增序列，但这题并不需要实现完整的操作

1
2
3

1  5   9
10 11 13
12 13 15

可以先窥探第一列，第一列是每一个行序列的最小值所组成的，因此第一列中的最小值毫无疑问是1，这里可以先弹出1，矩阵变为

1
2
3

   5  9
10 11 13
12 13 15

若要继续判断，只需要判断5, 10, 12中的最小值，然后继续弹出最小值

1
2
3

      9
10 11 13
12 13 15

1
2
3

       
10 11 13
12 13 15

1
2
3

   
   11 13
12 13 15

所以需要一个优先级队列来维护顶头最小，下面最大的一个堆，并且每个堆中的元素需要记录这个元素在矩阵中的坐标，从而可以在弹出后用它右边的元素接替。

代码如下：

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        priority_queue<Ele, vector<Ele>, less<Ele>> pq;
        int m = matrix.size(), n = matrix[0].size();
        for(int i = 0; i < m; ++i)
            pq.push(Ele(matrix[i][0], i, 0));
        for(int i = 0; i < k - 1; ++i)
        {
            auto p = pq.top();
            pq.pop();
            if(p.y == n - 1)
                continue;
            pq.push(Ele(matrix[p.x][p.y + 1], p.x, p.y + 1));
        }
        return pq.top().val;
    }
private:
    struct Ele {
        int val;
        int x;
        int y;
        Ele(int val, int x, int y) : val(val), x(x), y(y) {}
        bool operator < (const Ele& ele) const
        {
            return this->val > ele.val;
        }
    };
};

less：当左边小于右边时，return true

priority_queue：当新进来的数导致了顺序错误，则return true。此处是新进来的数如果大于顶头的数，就return true。

因此类中应当重载<操作符，当左边小于右边时return false，也就是左边大于右边时return true。

lhs < rhs时，调用的是lhs的重载操作符，所以需要lhs>rhs返回true，所以是this->val>ele.val。

使用二分查找

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int lo = matrix[0][0], hi = matrix.back().back();
        while(lo < hi)
        {
            auto mid = (hi + lo) >> 1;
            auto num = check(matrix, mid);
            // 如果使用num == k时候就返回，就会导致mid可能不是这区间里数
            if(num >= k)
                hi = mid;
            else if(num < k)
                lo = mid + 1;
        }
        return hi;
    }
private:
    int check(vector<vector<int>>& matrix, int mid)
    {
        int i = matrix.size() - 1;
        int j = 0;
        int num = 0;
        while(i >= 0 && j < matrix[0].size())
        {
            if(matrix[i][j] <= mid) // =mid时候要算入，因为需要的是他是第几个，而不是比他小的有几个
            {
                ++j;
                num += i + 1;
            }else
            {
                --i;
            }
        }
        return num;
    }
};

怎么保证最后的值是矩阵中的值?

当lo和hi相遇时，他们肯定收敛一个矩阵中具有的数值

若right不在矩阵中

当mid恰好大于解一点点的话，最终得到的面积会与k相等，解位于lo~mid内，这时候令hi=mid
当mid恰好小于解一点点的话，最终得到的面积会小于k，这时候hi不变，lo变为mid+1，为什么lo不是mid呢，因为当取lo==mid时，由于c++中除法向下取整，所以会导致无限循环。而hi如果取mid-1，就会导致区间将不再包括hi。而lo取mid+1则不会，因为这种情况下mid+1~hi中肯定有解。

如果right在矩阵中

与上述类似

所以，根据上述情况，解可以始终保证位于区间lo~hi之中，当lo和hi相等之时，就可以保证他们必定为解。