LeetCode378. 有序矩阵中第K小的元素 C++

方法一

解题思路

m行n列的矩阵每一行相当于一个排好序的数组，要求出第k大的数，需要对这m行一维数组进行最小堆的建立，选出第k大的元素。

可以用STL中的优先队列实现，这里实现需要定义一个结构体，同时对结构体的小于号也要进行重载。

结构体定义

struct Point{ int val; int x; int y; Point(){} Point(int _val, int _x, int _y): val(_val), x(_x), y(_y){} bool operator< (const Point p) const{ return val > p.val; } };

代码

class Solution { public: int kthSmallest(vector<vector<int>>& matrix, int k) { if(matrix.size() == 0 || matrix[0].size() == 0){ return 0; } int m = matrix.size(); int n = matrix[0].size(); struct Point{ int val; int x; int y; Point(){} Point(int _val, int _x, int _y): val(_val), x(_x), y(_y){} bool operator< (const Point p) const{ return val > p.val; } }; //用归并排序，归并k个元素，建立一个小根堆 priority_queue<Point> myQueue; //先将所有行开头的元素入队，顺便入队他的行号列号 for(int i = 0; i < m; ++i){ myQueue.push(Point(matrix[i][0], i, 0)); } //出队k次，将结果保存在ans中 Point ans; int i = 0; while(!myQueue.empty() && i < k){ ans = myQueue.top(); myQueue.pop(); i++; //将ans后面的元素入队 if(ans.y != n - 1){ myQueue.push(Point(matrix[ans.x][ans.y + 1], ans.x, ans.y + 1)); } } return ans.val; } };

复杂度分析

假设矩阵 n行，m列.

时间复杂度：插入的时间复杂度为 O(log n)，故总共 O(k logn)，最差 O(n*n logn)

空间复杂度：空间恒定为 O(n).

方法二

解题思路

数组中最小的值为 matrix[0][0] ，最大为 matrix[m - 1][n - 1] ，第k个数一定在他们值中间，定义变量 left 和 right 分别等于 matrix[0][0] 和 matrix[m - 1][n - 1]]。

选择 matrix[0][0] 和 matrix[m - 1][n - 1] 中间的数，用二分查找，以该数 mid 为分界线，将矩阵分为左右两个部分，求出比 mid 小的数在矩阵中的个数。

若小于mid值的个数大于等于k，证明mid太大了，right = mid。

否则，left = mid + 1。直到left = right。

代码

class Solution { public: int count(vector<vector<int>>& matrix, int mid){ int m = matrix.size(); int n = matrix[0].size(); int ans = 0; //从最后一行的第一个元素开始 int j = 0; for(int i = m - 1; i >= 0; --i){ while(j < n && matrix[i][j] <= mid){ ++j; } ans += j; } return ans; } int kthSmallest(vector<vector<int>>& matrix, int k) { if(matrix.size() == 0 || matrix[0].size() == 0){ return 0; } int m = matrix.size(); int n = matrix[0].size(); //方法二：二分查找 //数组中最小的值为matrix[0][0]，最大为matrix[m - 1][n - 1]，第k个数一定在他们值中间 int left = matrix[0][0], right = matrix[m - 1][n - 1]; while(left < right){ int mid = left + (right - left) / 2; //然后找mid值将数组分成的两部分分别的长度 if(count(matrix, mid) >= k){ right = mid; //注意！这里的mid已经可以将数分成k和m*n-k了，但是也许不是最终答案， //还需要向前找最小的能将矩阵分成k和m*n-k的数，而且这个最小数一定存在于数组中 } else{ left = mid + 1; } } return left; } };

复杂度分析

时间复杂度：O(n log n)，查找次数 O(logn)，每次操作次数 O(n).

空间复杂度： O(1).