Leetocode 378 Kth Smallest Element in a Sorted Matrix

Question

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

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

return 13.

 

처음 생각한 간단한 방식은

matrix를 flatten 한 뒤 그 리스트의 k-1번째 인덱스를 리턴하면 될 듯하여 만든 코드입니다.

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        import operator
        temp = reduce(operator.concat, matrix)
        return sorted(temp)[k-1]
        

numpy.flatten() 대신에 사용할만한 것을 찾다 보니 operator.concat을 사용하면 된다고 해서 사용해 봤습니다. 

 

그 외에 stackoverflow에서 다양한 테스트를 해주신 분 있어서 참고하면 좋을 듯 합니다. 

https://stackoverflow.com/questions/952914/how-to-make-a-flat-list-out-of-list-of-lists

How to make a flat list out of list of lists?

 

 

.reduce()

def int_sum(x1, x2):
	return x1 + x2
    
from functools import reduce
reduce(int_sum, [1,2,3,4])

# 10