เมื่อจำเป็นต้องเลือกองค์ประกอบที่ใหญ่เป็นอันดับที่ n จากรายการในความซับซ้อนของเวลาเชิงเส้น ต้องใช้สองวิธี วิธีหนึ่งในการหาองค์ประกอบที่ใหญ่ที่สุด และอีกวิธีหนึ่งที่แบ่งรายการออกเป็นสองส่วน ส่วนนี้ขึ้นอยู่กับค่า 'i' ที่ผู้ใช้กำหนด ตามค่านี้ รายการจะถูกแยกออกและกำหนดองค์ประกอบที่ใหญ่ที่สุด
ด้านล่างนี้เป็นการสาธิตสิ่งเดียวกัน -
ตัวอย่าง
def select_largest(my_list, beg, end, i):
if end - beg <= 1:
return my_list[beg]
pivot_val = start_partition(my_list, beg, end)
k = end - pivot_val
if i < k:
return select_largest(my_list, pivot_val + 1, end, i)
elif i > k:
return select_largest(my_list, beg, pivot_val, i - k)
return my_list[pivot_val]
def start_partition(my_list, beg, end):
pivot_val = my_list[beg]
i = beg + 1
j = end - 1
while True:
while (i <= j and my_list[i] <= pivot_val):
i = i + 1
while (i <= j and my_list[j] >= pivot_val):
j = j - 1
if i <= j:
my_list[i], my_list[j] = my_list[j], my_list[i]
else:
my_list[beg], my_list[j] = my_list[j], my_list[beg]
return j
my_list = input('Enter the list of numbers.. ')
my_list = my_list.split()
my_list = [int(x) for x in my_list]
i = int(input('Enter the value for i.. '))
ith_largest = select_largest(my_list, 0, len(my_list), i)
print('The result is {}.'.format(ith_largest)) ผลลัพธ์
Enter the list of numbers.. 34 67 12 0 999 Enter the value for i.. 1 The result is 999.
คำอธิบาย
-
มีการกำหนดเมธอดที่ชื่อว่า 'select_largest' ซึ่งรับรายการ จุดเริ่มต้น จุดสิ้นสุด และค่า 'i' เป็นพารามิเตอร์
-
มีการกำหนดวิธีการอื่นที่เรียกว่า 'start_partition' ซึ่งแบ่งรายการออกเป็นสองส่วนขึ้นอยู่กับค่าของ 'i'
-
วิธีนี้เรียกว่าเมธอด 'select_largest'
-
'select_largest' จะถูกเรียกอีกครั้งภายในฟังก์ชันเดียวกัน นี่คือวิธีการทำงานของการเรียกซ้ำ
-
ตัวเลขจะถูกนำมาเป็นอินพุตจากผู้ใช้
-
โดยจะแบ่งตามค่าเริ่มต้น
-
ซ้ำแล้วซ้ำเล่า
-
ค่าสำหรับ 'i' ถูกนำมาจากผู้ใช้
-
ตามค่า 'i' นี้ รายการจะถูกแบ่งออกเป็นสองส่วน
-
วิธี 'select_largest' ถูกเรียกในรายการใดรายการหนึ่ง
-
เอาต์พุตจะแสดงบนคอนโซล
