Chương trình tìm ra tích lớn thứ k của các phần tử của hai mảng trong Python

Giả sử chúng ta được cung cấp hai danh sách, p và q chứa một số số nguyên. Chúng ta phải nhân tất cả các giá trị của các danh sách này và phải tìm ra giá trị lớn nhất thứ k từ kết quả phép nhân.

Vì vậy, nếu đầu vào là p =[2, 5], q =[6, 8], k =2, thì đầu ra sẽ là 16.

Kết quả phép nhân là:2 * 6 =12, 2 * 8 =16, 5 * 6 =30, 5 * 8 =40. Phần tử lớn thứ 2 tại là (chỉ số bắt đầu từ 0) là 16.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• sắp xếp danh sách p
• sắp xếp danh sách q
• k:=k + 1
• heap:=một heap mới trong biểu diễn danh sách
• đối với mỗi độ cao trong q, thực hiện
  • nếu elem> =0, thì
    • đối với tôi trong phạm vi (kích thước của p - 1) đến -1, giảm đi 1, thực hiện
      • cd:=elem * p [i]
      • nếu heap không trống và kích thước của heap giống k và cd <=heap [0] thì
        • ra khỏi vòng lặp
      • chèn giá trị cd vào heap
      • if length of (heap)> k, then
        • xóa mục nhỏ nhất khỏi heap
  • nếu không,
    • đối với tôi trong phạm vi từ 0 đến kích thước là p, thực hiện
      • cd:=elem * p [i]
      • nếu heap không trống và kích thước của heap giống k và cd <=heap [0] thì
        • ra khỏi vòng lặp
      • chèn cd vào heap
      • nếu length of (heap)> k khác 0, thì
        • xóa mục nhỏ nhất khỏi vòng lặp
• return heap [0]

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

from heapq import heappush, heappop
def solve(p, q, k):
p = sorted(p)
q = sorted(q)
k += 1
heap = []
for elem in q:
if elem >= 0:
for i in range((len(p) - 1), -1, -1):
cd = elem * p[i]
if heap and len(heap) == k and cd <= heap[0]:
break
heappush(heap, cd)
if len(heap) > k:
heappop(heap)
else:
for i in range(len(p)):
cd = elem * p[i]
if heap and len(heap) == k and cd <= heap[0]:
break
heappush(heap, cd)
if len(heap) > k:
heappop(heap)
return heap[0]
print(solve([2, 5], [6, 8], 2))

Đầu vào

[2, 5], [6, 8], 2

Đầu ra

16