leetcode

Kth Smallest Element in a Sorted Matrix

Kth Smallest Element in a Sorted Matrix

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import heapq
class Solution(object):
    def kthSmallest(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        return list(heapq.merge(*matrix))[k-1]
        
        
In [11]: heapq.merge?
Signature: heapq.merge(*iterables)
Docstring:
Merge multiple sorted inputs into a single sorted output.
Similar to sorted(itertools.chain(*iterables)) but returns a generator,
does not pull the data into memory all at once, and assumes that each of
the input streams is already sorted (smallest to largest).
>>> list(merge([1,3,5,7], [0,2,4,8], [5,10,15,20], [], [25]))
[0, 1, 2, 3, 4, 5, 5, 7, 8, 10, 15, 20, 25]

test code

1
2
3
4
In [104]: s = Solution(); t = s.kthSmallest([[1,5,9],[10,11,13],[12,13,15]], 8)
In [105]: print t
13

leet code