leetcode Kth Smallest Element in a Sorted Matrix

leetcode Kth Smallest Element in a Sorted Matrix

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.

Example:

Note:
You may assume k is always valid, 1 ≤ k ≤ n2.

题目地址:leetcode Kth Smallest Element in a Sorted Matrix

题意:给定一个每一行每一列都排好序的矩阵,求其中第k大的元素

思路:

先想到的就是用堆。直接维护一个大小为k的堆,全部读入一遍,这样平均和最坏情况都为O(n^2 *  logk) 很暴力,没有利用有序的特点。

因为每一行和每一列都是有序的了,因此维护一个最小堆,每次取出堆顶的元素,然后把它下方的元素放进堆(如果是第一行,还要把它右边的元素放入,这样不会重复。)

这样做K次后堆顶元素就是第K大的了。这样复杂度为多少呢?O(KlogK) 然而K最坏情况是n^2….. 因此,这个方法也一般。

PS: 本来写k  – – > 0 的,想到以前知乎上看到的 C语言有啥奇技淫巧, – – >是趋向于, 哈哈哈~ 一本正经的胡说八道

 

 

我觉得用二分做最好,这个方法只要求行有序,和列有木有序并没有关系。 (或者列有序,行有序无序都没关系)

设L = min(matrix) R= max(matrix)  , mid =( L + R ) / 2 ,mid为我们猜测的答案。

然后对于每一行,找它在该行中第几大(也是二分,找上界),累加和K比较。

值得注意的是枚举 答案应该用下界, 因为猜想的解不一定在数组中,不断的收缩直到找到在数组中的元素为止。

查找一行需要log(n) ,有n行所以nlog(n),最坏下需要查找log(X)次(X= int最大值的时候logX仅仅才为32),X为最大最小数差值。  所以总复杂度为O(nlogn *  logX)

PS:其实是我一开始看成就行有序→_→,然后就直接二分了

C++

Java

Python

 

 

上述的解法并没有利用到列有序的性质。

而下面的解法利用了列有序的性质,并将复杂度降到了O(nlogX)   其中X = max – min

我们仍采用猜测法,设L = min(matrix) R= max(matrix) , mid =( L + R ) / 2 ,mid为我们猜测的答案。

对于mid,我们不必再所有的行或列种执行二分查找,我们可以从左下角出发,若matrix[i][j] <= mid,则下一次查询在右边(j++),并且,该列的所有元素均比mid小,因此可以cnt += (i+1)

对于matrix[i][j] > mid,则 i – – 。 过程类似于240. Search a 2D Matrix II  (题解在最下方)

C++

Java

Python

 

当然也可以从右上角到左下角,以Python为例,相应的函数改成如下即可:

 

 

本题是leetcode 378 Kth Smallest Element in a Sorted Matrix题解

更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Kth Smallest Element in a Sorted Matrix
本文地址:https://www.hrwhisper.me/leetcode-kth-smallest-element-sorted-matrix/

打赏一杯咖啡钱呗

Leetcode , , , , . permalink.

7 thoughts on “leetcode Kth Smallest Element in a Sorted Matrix

  1. while (L > 1);
    int temp = 0;
    for (int i = 0; i < n; i++) temp += upper_bound(matrix[i].begin(), matrix[i].end(), mid) – matrix[i].begin();
    if (temp < k) L = mid + 1;
    else R = mid;
    }

    不懂的是為什麼是在while迴圈的最後

    是else hi = mid; 而不是 else hi = mid – 1;

    我有自己代數字實際跑一遍, else hi = mid; 是正確的,但是卻不知道為什麼這是正確

    也不懂為什麼 hi = mid – 1就不行

  2. 大神问一下,为什么当L,R 相等的时候一定是第k个在matrix里的数字? 当L=R的时候,有可能这个数字不在matrix 里吗?

Leave a Reply

Your email address will not be published. Required fields are marked *