遵化建设招标网站,无锡新吴区建设环保局网站,山东建设局网站,本机网络ip做网站问题简述
给定一个 nn的矩阵#xff0c;矩阵中每行和每列的元素都按升序排列。给定一个 k(k∈[1,n2])#xff0c; 求再整个矩阵中按从小到大排序为 k的元素。
例如：matrix = [[ 1, 5, 9],[10, 11, 13],[12, 13, 15]
],
k = 8,return 13.解题思路该矩阵的行和列都是按从小…问题简述
给定一个 n×nn \times n 的矩阵矩阵中每行和每列的元素都按升序排列。给定一个 k(k∈[1,n2])k (k \in [1, n^2]) 求再整个矩阵中按从小到大排序为 kk 的元素。
例如：matrix = [[ 1, 5, 9],[10, 11, 13],[12, 13, 15]
],
k = 8,return 13.解题思路该矩阵的行和列都是按从小到大的顺序排列的，这样的问题一般都是可以用二分法解决的。再来看，我们的输入 kk输出是第 kk 大的元素，不难发现，kk 越大输出的元素也就越大。好了决定用二分法了~ 首先我们以整个矩阵中的最小值为下边界左上角元素最大值为上边界右下角元素。然后用二分的方法猜过去猜输出的结果是多少。只要满足猜的条件我们就会把整个元素记录下来然后看看有没有比这个元素小并且满足猜的条件的元素。这个过程的时间复杂度为 O( log(maxVal−minVal) )O(\ log(maxVal-minVal)\ )其中的 minValminVal 为矩阵左上角的元素maxValmaxVal 为矩阵右下角的元素。 好了接下来就是看看怎么猜了~ 这里猜的时候又用到了一次二分法其目的是找到每行中不大于猜的值 valval 的数有多少然后算出整个矩阵中不大于 valval 的数有多少。如果不大于 valval 的数大于 kk 则返回true，否则返回false。这个过程的时间复杂度为 O(nlog(n))O(\ nlog(n)\ )。这一步是可以进一步优化的~ 这个过程的时间复杂度为 O( nlog(n)log(maxVal−minVal) )O(\ nlog(n)log(maxVal-minVal)\ )。 最后上代码~
代码
class Solution {
private:bool guess(vectorvectorint matrix, int k, int val){for (int i 0; i matrix.size(); i){int left 0;int right matrix[i].size() - 1;int ans 0;while (left right){int mid left (right - left) / 2;if (matrix[i][mid] val){left mid 1;ans mid 1;}else{right mid - 1;}}k - ans;if (k 1)return true;}return false;}public:int kthSmallest(vectorvectorint matrix, int k) {int n matrix.size();int left matrix[0][0];int right matrix[n - 1][n - 1];int ans;while (left right){int mid left (right - left) / 2;if (guess(matrix, k, mid)){ans mid;right mid - 1;}else{left mid 1;}}return ans;}
};
