Chương trình tìm số nhỏ thứ n từ ma trận đã sắp xếp trong Python

Mô tả bài toán

Cho ma trận 2D, mỗi hàng và cột sắp xếp không giảm. Tìm số nhỏ thứ n (0-indexed).

Ví dụ: ma trận [[2,4,30],[3,4,31],[6,6,32]], n = 4 → đầu ra 6.

Giải thuật (Làm phẳng và sắp xếp)

1. Tạo danh sách lst chứa tất cả phần tử ma trận.
2. Sắp xếp lst.
3. Trả về lst[n].

Lưu ý: Giải pháp này đơn giản nhưng không tối ưu cho ma trận lớn. Có thể dùng heap hoặc binary search để tối ưu.

Ví dụ mã Python

class Solution:
    def solve(self, matrix, n):
        lst = []
        for i in matrix:
            for j in i:
                lst.append(j)
        lst.sort()
        return lst[n]

ob = Solution()
matrix = [[2, 4, 30], [3, 4, 31], [6, 6, 32]]
n = 4
print(ob.solve(matrix, n))

Đầu vào

matrix = [ [2, 4, 30], [3, 4, 31], [6, 6, 32] ] n = 4

Đầu ra

6