Chương trình Python để chọn phần tử lớn nhất thứ n từ danh sách trong thời gian tuyến tính mong đợi

Khi cần chọn phần tử lớn thứ n từ danh sách theo độ phức tạp thời gian tuyến tính, cần có hai phương pháp. Một phương pháp để tìm phần tử lớn nhất và một phương pháp khác chia danh sách thành hai phần. Sự phân chia này phụ thuộc vào giá trị ‘i’ do người dùng cung cấp. Dựa trên giá trị này, danh sách được tách và phần tử lớn nhất được xác định.

Dưới đây là một minh chứng về điều tương tự -

Ví dụ

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))

Đầu ra

Enter the list of numbers.. 34 67 12 0 999
Enter the value for i.. 1
The result is 999.

Giải thích

• Phương thức có tên ‘select_largest’ được xác định, phương thức này nhận danh sách, phần đầu, phần cuối và giá trị ‘i’ được lấy làm tham số.

• Một phương thức khác có tên là ‘start_partition’ được định nghĩa để chia danh sách thành hai phần tùy thuộc vào giá trị của ‘i’.

• Phương thức này được gọi trong phương thức ‘select_largest’.

• ‘Select_largest’ cũng được gọi lại bên trong cùng một hàm - đây là cách hoạt động của đệ quy.

• Các số được lấy làm đầu vào từ người dùng.

• Nó được phân chia dựa trên giá trị mặc định.

• Nó được lặp lại.

• Giá trị cho ‘i’ được lấy từ người dùng.

• Dựa trên giá trị ‘i’ này, danh sách được chia thành hai phần.

• Phương thức ‘select_largest’ được gọi trên một trong các danh sách.

• Đầu ra được hiển thị trên bảng điều khiển.