Cho hai danh sách p, q chứa số nguyên. Nhân từng cặp (mỗi phần tử p với mỗi phần tử q). Tìm giá trị lớn thứ k (0-indexed) trong các kết quả nhân.
Ví dụ
Input: p=[2,5], q=[6,8], k=2 → Output: 16
Các tích: 2×6=12, 2×8=16, 5×6=30, 5×8=40. Sắp xếp: [12, 16, 30, 40]. Phần tử index 2 = 16.
Thuật toán (Min-Heap kích thước k+1)
Sắp xếp cả hai mảng. Duyệt q, với mỗi phần tử q_j, nhân với p theo thứ tự phù hợp (giảm dần nếu q_j≥0, tăng dần nếu q_j<0) để sinh tích theo thứ tự giảm dần. Dùng min-heap giữ k+1 phần tử lớn nhất.
- Sắp xếp p, q
- k := k + 1 (vì 0-indexed)
- Với mỗi elem trong q:
- elem ≥ 0: nhân với p từ lớn đến nhỏ (p[i] giảm dần)
- elem < 0: nhân với p từ nhỏ đến lớn (p[i] tăng dần)
- Đẩy vào heap, nếu heap size > k thì pop phần tử nhỏ nhất
- Dừng sớm nếu tích hiện tại ≤ heap[0] (vì p đã sắp xếp, các tích sau chỉ nhỏ hơn)
- Trả về heap[0] (phần tử nhỏ nhất trong k phần tử lớn nhất = lớn thứ k)
Mã nguồn
from heapq import heappush, heappop
def solve(p, q, k):
p = sorted(p)
q = sorted(q)
k += 1 # chuyển sang 1-indexed cho heap size
heap = []
for elem in q:
if elem >= 0:
# Nhân với p từ lớn đến nhỏ
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:
# Nhân với p từ nhỏ đến lớn (vì âm * âm = dương, âm * dương = âm)
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)) # Output: 16Độ phức tạp
- Thời gian: O(n log n + m log m + m × min(n, k) log k)
- Không gian: O(k)
- Tối ưu hơn brute-force O(nm log nm) khi k nhỏ