กำหนดลิสต์จำนวนเต็ม งานคือหา N ค่าที่มากที่สุดในลิสต์
ตัวอย่าง
Input: [40, 5, 10, 20, 9]
N = 2
Output: [40, 20]
อัลกอริทึม (วิธีที่ 1: Traverse และ Remove)
- รับลิสต์จำนวนเต็มและจำนวน N
- วนลูป N รอบ
- แต่ละรอบหาค่าสูงสุด เก็บในลิสต์ใหม่ แล้วลบออกจากลิสต์เดิม
โค้ดตัวอย่าง (วิธีที่ 1)
def N_largest_elements(list1, N):
new_list = []
for i in range(N):
max1 = 0
for j in range(len(list1)):
if list1[j] > max1:
max1 = list1[j]
list1.remove(max1)
new_list.append(max1)
print("Largest numbers are:", new_list)
# Driver code
my_list = [12, 61, 41, 85, 40, 13, 77, 65, 100]
N = 4
N_largest_elements(my_list, N)
ผลลัพธ์
Largest numbers are: [100, 85, 77, 65]
วิธีที่ 2: ใช้ sorted() (ง่ายและ Pythonic)
def n_largest_sorted(lst, n):
return sorted(lst, reverse=True)[:n]
my_list = [12, 61, 41, 85, 40, 13, 77, 65, 100]
print(n_largest_sorted(my_list, 4)) # [100, 85, 77, 65]
วิธีที่ 3: ใช้ heapq.nlargest() (มีประสิทธิภาพมากที่สุด)
import heapq
my_list = [12, 61, 41, 85, 40, 13, 77, 65, 100]
print(heapq.nlargest(4, my_list)) # [100, 85, 77, 65]
การเปรียบเทียบ
| วิธี | Time Complexity | Space | หมายเหตุ |
|---|---|---|---|
| Traverse + Remove | O(N × n) | O(N) | แก้ไขลิสต์เดิม ช้า |
| sorted() | O(n log n) | O(n) | เรียงทั้งลิสต์ |
| heapq.nlargest() | O(n log N) | O(N) | เร็วที่สุดสำหรับ N ≪ n |
วิธีที่ 4: ใช้ nlargest กับ key function
# หา 3 dictionary ที่มี 'score' มากที่สุด
data = [
{'name': 'Alice', 'score': 85},
{'name': 'Bob', 'score': 92},
{'name': 'Charlie', 'score': 78},
{'name': 'David', 'score': 96}
]
top3 = heapq.nlargest(3, data, key=lambda x: x['score'])
print(top3)
# [{'name': 'David', 'score': 96}, {'name': 'Bob', 'score': 92}, {'name': 'Alice', 'score': 85}]
สรุป: ใช้ heapq.nlargest() สำหรับประสิทธิภาพดีที่สุด โดยเฉพาะตอน N เล็กกว่า n มาก
