题目描述

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

题意：给一个行有序且列有序的二维数组，找出其中第K小的数。

样例

matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,return 13.

算法1 大顶堆

题解1:维护一个K个元素的大顶堆，那么堆顶元素就是第K小的数，遍历整个数组，如果这个数大于堆顶元素，说明这个数不是第K小的，如果这个数比堆顶元素小，那么弹出堆顶元素，将这个数插入堆中。C++中用优先队列priority_queue实现。没有利用行有序和列有序的性质，时间复杂度$O(n^2logK)

C++ 代码

  int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        //升序队列
        //priority_queue <int,vector<int>,greater<int> > q;
        //降序队列
        //priority_queue <int,vector<int>,less<int> >q;
        //c++默认是降序队列，即大顶堆
        priority_queue<int> q;
        for(int i = 0 ; i < n ; i ++)
        {
            for(int j = 0 ; j < n ; j++)
            {
                if(q.size() < k)
                    q.push(matrix[i][j]);
                else
                {
                    if(matrix[i][j] < q.top())
                    {
                        q.pop();
                        q.push(matrix[i][j]);
                    }
                }
            }
        }
        return q.top();
  }

算法2

题解2:二分搜索的题型分为两种，一种是索引二分(在有序数组中二分查找)，一种是值域二分（可行解在一个区间内查找，判断这个解是否成立）。这题就是经典的值域二分问题可以解的问题，首先数组的最小值是左上角的$matrix[0][0]$，最大值是右下角的$matrix[n-1][n-1]$，那么第$k$小的数一定在这个区间内。

那么遍历整个数组，如果数组中的数小于等于target的元素小于K个，那么说明第K小的数比target大。如果数组中的数小于等于target的元素大于等于K个，就说明第K小的数小于等于target。题意：找一个最小的target，使得数组中小于等于target的数大于等于K。二分查找模板二：找大于某个数中的最小值。 二分查找边界模板详解

遍历每一行的时候如果遇到一个比target大的数字，就不用继续遍历了，因为行是升序的。这种方法没有利用列有序的性质。

那么每统计一次小于等于target的个数，需要$O(n^2)$的时间复杂度，总的时间复杂度为$O(n^2logL)$，$L$代表数组最大值和最小值的差。

C++ 代码

int search(vector<vector<int>>& matrix, int target,int n)
{
            int count = 0;//也可以使用lowerbound函数来完成这个函数，这里为了和解法三对比。
            for(int i = 0 ; i < n ; i ++)
            {
                for(int j = 0 ; j < n ; j ++)
                {
                    if(matrix[i][j] <= target)
                    {
                        count ++ ;
                        continue;
                    }//行有序，遇到第一个大于mid的数就跳出。
                    break;
                }
            }
  return count
}
int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        int left = matrix[0][0],right = matrix[n - 1][n - 1];
        //数组元素小于等于target的个数大于等于k的最小target，二分模板二
        //值域上的二分搜索
        while(left < right)
        {
            int mid = (left + right)/2;
                count = search(matrix,mid,n);
            if(count >= k)
                right = mid;
            else
                left = mid + 1;
        }
        return left;
  }

算法3

题解3:为了利用行有序和列有序这两个性质，我们考虑如下一种做法来统计数组中小于等于target的数的个数。那么美统计一次小于等于target的个数，只需要$O(n)$的时间复杂度，总的时间复杂度为$O(nlogL)$，$L$代表数组最大值和最小值的差。

C++ 代码

    int search(vector<vector<int>>& matrix, int target,int n)
    {
        //先从数组左下角元素开始,代表了从当前位置到右上角元素的矩形区域是还没有遍历的区间
        int row = n - 1 ,col = 0;
        int count = 0;
        while(row >=0 && col < n)
        {
            //如果这个当前数组元素小于目标值，说明这个元素以及同列的上方元素都小于目标值。
            //那么count加上row + 1,因为这一列已经遍历过了所以同时把col + 1，
            if(matrix[row][col] <= target)
            {
                count += row + 1;
                col ++;
            }else{//如果当前数组元素大于目标值，则这个元素以及同行的右方元素都大于目标值，
              //因为这一行已经遍历过了，所以col-1
                row --;
            }
        }
        return count;
    }
  int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        int left = matrix[0][0],right = matrix[n - 1][n - 1];
        //数组元素小于等于target的个数大于等于k的最小target，二分模板二
        //值域上的二分搜索
        while(left < right)
        {
            int mid = (left + right)/2;
            int count = search(matrix,mid,n);
            if(count >= k)
                right = mid;
            else
                left = mid + 1;
        }
        return left;
  }