Chương trình Python tìm phần tử nhỏ thứ k trong mảng 2D

Cho ma trận n×n số nguyên nhập từ người dùng và giá trị k. Nhiệm vụ tìm phần tử nhỏ thứ k trong mảng 2D. Dùng module heapq. Heap queue (heapq) trong Python. Kỹ thuật này mỗi lần pop phần tử nhỏ nhất của heap (min heap). Phương thức nsmallest() dùng để lấy n giá trị nhỏ nhất từ data frame hoặc series.

Ví dụ

Input Array is:: 10 20 20 40 15 45 40 30 32 33 30 50 12 78 99 78
The value of k is 10
10 th smallest element is 40

Thuật toán

Bước 1: Tạo mảng 2D.
Bước 2: Gán hàng đầu cho biến và chuyển thành min heap.
Bước 3: Duyệt các hàng còn lại và push phần tử vào min heap.
Bước 4: Dùng nsmallest(k, iterable) của heapq lấy list k phần tử nhỏ nhất, in phần tử cuối của list đó.

Ví dụ mã

# Chương trình Python tìm K'th smallest element trong mảng 2D
import heapq

def smallestele(A):
    assignval = A[0]
    heapq.heapify(assignval)
    for i in A[1:]:
        for j in i:
            heapq.heappush(assignval, j)
    mini = heapq.nsmallest(k, assignval)
    print(k, "th smallest element is ", mini[-1])

# Driver program
if __name__ == "__main__":
    A = []
    n = int(input("Enter N for N x N matrix: "))
    print("Enter the element ::>")
    for i in range(n):
        row = []
        for j in range(n):
            row.append(int(input()))
        A.append(row)
    print(A)
    print("Display Array In Matrix Form")
    for i in range(n):
        for j in range(n):
            print(A[i][j], end=" ")
        print()
    k = int(input("Enter the kth position ::>"))
    smallestele(A)

Kết quả

Enter N for N x N matrix : 4
Enter the element ::>
10
20
20
40
15
45
40
30
32
33
30
50
12
78
99
78
[[10, 20, 20, 40], [15, 45, 40, 30], [32, 33, 30, 50], [12, 78, 99, 78]]
Display Array In Matrix Form
10 20 20 40
15 45 40 30
32 33 30 50
12 78 99 78
Enter the kth position ::>10
10 th smallest element is 40