파이썬에서 두 배열 요소의 k번째로 큰 곱을 찾는 프로그램

<시간/>

일부 정수를 포함하는 두 개의 목록 p와 q가 주어졌다고 가정합니다. 이 목록의 모든 값을 곱해야 하고 곱한 결과에서 k번째로 큰 값을 찾아야 합니다.

따라서 입력이 p =[2, 5], q =[6, 8], k =2와 같으면 출력은 16이 됩니다.

곱셈 결과는 2 * 6 =12, 2 * 8 =16, 5 * 6 =30, 5 * 8 =40입니다. 에서 두 번째로 큰 요소는 (인덱스가 0에서 시작) 16입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

목록 정렬
목록 q 정렬
k :=k + 1
힙 :=목록 표현의 새 힙
q의 각 요소에 대해 다음을 수행합니다.
- 요소>=0이면
  - i 범위(p - 1의 크기)에서 -1까지, 1만큼 감소, do
    - cd :=요소 * 피[i]
    - 힙이 비어 있지 않고 힙의 크기가 k 및 cd <=heap[0]과 같으면
      - 루프에서 나오다
    - 힙에 값 cd 삽입
    - (힙) 길이> k이면
      - 힙에서 가장 작은 항목 삭제
- 그렇지 않으면
  - 0~p 크기 범위의 i에 대해
    - cd :=요소 * 피[i]
    - 힙이 비어 있지 않고 힙의 크기가 k 및 cd <=heap[0]과 같으면
      - 루프에서 나오다
    - 힙에 CD 삽입
    - (힙)의 길이> k가 0이 아니면
      - 루프에서 가장 작은 항목 삭제
반환 힙[0]

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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

입력

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