โปรแกรม Python หาอิลิเมนต์ที่ n เล็กที่สุดใน 2D Array ด้วย heapq

หาอิลิเมนต์ที่ k-th smallest ในเมทริกซ์ n×n โดยใช้ heapq (min-heap) และ nsmallest()

ตัวอย่าง

Matrix 4x4, k=10 -> 10th smallest = 40

อัลกอริทึม

1. สร้าง 2D array
2. นำแถวแรก heapify เป็น min-heap
3. เข้าแถวที่เหลือ heappush ทุกอิลิเมนต์
4. ใช้ heapq.nsmallest(k, heap) แล้วเอาตัวสุดท้าย

โค้ดตัวอย่าง

import heapq

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

if __name__ == "__main__":
    A = []
    n = int(input("Enter N for N x N matrix: "))
    print("Enter the elements:")
    for _ in range(n):
        row = [int(input()) for _ in range(n)]
        A.append(row)
    k = int(input("Enter the kth position: "))
    smallestele(A, k)

ผลลัพธ์

Enter N for N x N matrix: 4
Enter the elements: 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