Kth Smallest Product of Two Sorted Arrays (LeetCode 2040)
Đề bài
LeetCode 2040 – Kth Smallest Product of Two Sorted Arrays (Tích nhỏ thứ k của hai mảng đã sắp xếp) – độ khó Hard.
Cho hai mảng số nguyên nums1 và nums2 đã được sắp xếp (tăng dần), đánh số từ 0, cùng một số nguyên $k$. Hãy trả về tích nhỏ thứ $k$ (đếm từ 1) trong các tích nums1[i] * nums2[j] với $0 \le i \lt$ nums1.length và $0 \le j \lt$ nums2.length.
Ràng buộc:
- $1 \le$
nums1.length,nums2.length$\le 5 \cdot 10^4$ - $-10^5 \le$
nums1[i],nums2[j]$\le 10^5$ - $1 \le k \le$
nums1.length$\times$nums2.length nums1vànums2đã được sắp xếp.
Ví dụ 1:
Input: nums1 = [2,5], nums2 = [3,4], k = 2
Output: 8Giải thích: 2 tích nhỏ nhất là:
nums1[0] * nums2[0] = 2 * 3 = 6nums1[0] * nums2[1] = 2 * 4 = 8
Tích nhỏ thứ 2 là 8.
Ví dụ 2:
Input: nums1 = [-4,-2,0,3], nums2 = [2,4], k = 6
Output: 0Giải thích: 6 tích nhỏ nhất là:
nums1[0] * nums2[1] = (-4) * 4 = -16nums1[0] * nums2[0] = (-4) * 2 = -8nums1[1] * nums2[1] = (-2) * 4 = -8nums1[1] * nums2[0] = (-2) * 2 = -4nums1[2] * nums2[0] = 0 * 2 = 0nums1[2] * nums2[1] = 0 * 4 = 0
Tích nhỏ thứ 6 là 0.
Ví dụ 3:
Input: nums1 = [-2,-1,0,1,2], nums2 = [-3,-1,2,4,5], k = 3
Output: -6Giải thích: 3 tích nhỏ nhất là:
nums1[0] * nums2[4] = (-2) * 5 = -10nums1[0] * nums2[3] = (-2) * 4 = -8nums1[4] * nums2[0] = 2 * (-3) = -6
Tích nhỏ thứ 3 là -6.
2040. Kth Smallest Product of Two Sorted Arrays – Hard
Given two sorted 0-indexed integer arrays nums1 and nums2 as well as an integer k, return the kth (1-based) smallest product of nums1[i] * nums2[j] where 0 <= i < nums1.length and 0 <= j < nums2.length.
Constraints:
1 <= nums1.length, nums2.length <= 5 * 104-105 <= nums1[i], nums2[j] <= 1051 <= k <= nums1.length * nums2.lengthnums1andnums2are sorted.
Example 1:
Input: nums1 = [2,5], nums2 = [3,4], k = 2
Output: 8
Explanation: The 2 smallest products are:
- nums1[0] * nums2[0] = 2 * 3 = 6
- nums1[0] * nums2[1] = 2 * 4 = 8
The 2nd smallest product is 8.Example 2:
Input: nums1 = [-4,-2,0,3], nums2 = [2,4], k = 6
Output: 0
Explanation: The 6 smallest products are:
- nums1[0] * nums2[1] = (-4) * 4 = -16
- nums1[0] * nums2[0] = (-4) * 2 = -8
- nums1[1] * nums2[1] = (-2) * 4 = -8
- nums1[1] * nums2[0] = (-2) * 2 = -4
- nums1[2] * nums2[0] = 0 * 2 = 0
- nums1[2] * nums2[1] = 0 * 4 = 0
The 6th smallest product is 0.Example 3:
Input: nums1 = [-2,-1,0,1,2], nums2 = [-3,-1,2,4,5], k = 3
Output: -6
Explanation: The 3 smallest products are:
- nums1[0] * nums2[4] = (-2) * 5 = -10
- nums1[0] * nums2[3] = (-2) * 4 = -8
- nums1[4] * nums2[0] = 2 * (-3) = -6
The 3rd smallest product is -6.Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.
class Solution. Để các bạn chạy thử được trên máy (hoặc trang Chạy code online), mọi code trong bài đều có thêm hàm main đọc từ bàn phím theo định dạng: dòng 1 gồm 3 số $n$, $m$, $k$ (độ dài nums1, độ dài nums2 và $k$); dòng 2 gồm $n$ số của nums1; dòng 3 gồm $m$ số của nums2. In ra một số nguyên là tích nhỏ thứ $k$. Ví dụ 2 sẽ nhập là:4 2 6
-4 -2 0 3
2 4Tóm tắt đề bài: cho 2 dãy số $a$ (độ dài $n$) và $b$ (độ dài $m$), đã sắp xếp tăng dần. Hãy liệt kê tích $a[i] \cdot b[j]$ với mọi cặp $(i, j)$, tức là $n \cdot m$ tích. Ta sắp xếp các số đã liệt kê tăng dần, hãy đưa ra số đứng thứ $K$ trong danh sách sau khi sắp xếp (số nhỏ thứ $K$, tính cả các số bằng nhau).
Ví dụ 2: các tích là $(-4) \cdot 2 = -8$, $(-4) \cdot 4 = -16$, $(-2) \cdot 2 = -4$, $(-2) \cdot 4 = -8$, $0, 0$, $3 \cdot 2 = 6$, $3 \cdot 4 = 12$. Sắp xếp: $-16, -8, -8, -4, 0, 0, 6, 12$ ⇒ số thứ 6 là 0. Cái khó của bài là có số âm: nhân với số âm thì thứ tự bị đảo ngược, nên tích nhỏ nhất không nằm ở "góc" nào cố định cả.
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Làm theo đề: liệt kê hết rồi sắp xếp – O(nm log(nm))
Cách tự nhiên nhất là làm đúng như đề nói: tính hết $n \cdot m$ tích (nhớ dùng long long, vì tích có thể tới $10^{10}$), sắp xếp tăng dần rồi lấy phần tử thứ $k$ (chỉ số $k - 1$).
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
long long kthSmallestProduct(vector<int>& a, vector<int>& b, long long k) {
vector <long long> p;
for (int i = 0; i < (int) a.size(); i++) {
for (int j = 0; j < (int) b.size(); j++) {
p.push_back(1LL * a[i] * b[j]);
}
}
sort(p.begin(), p.end());
return p[k - 1];
}
};
int main() {
int n, m;
long long k;
cin >> n >> m >> k;
vector<int> a(n), b(m);
for (int i = 0; i < n; i++) cin >> a[i];
for (int j = 0; j < m; j++) cin >> b[j];
Solution sol;
cout << sol.kthSmallestProduct(a, b, k);
return 0;
}import sys
from typing import List
class Solution:
def kthSmallestProduct(self, a: List[int], b: List[int], k: int) -> int:
p = [x * y for x in a for y in b]
p.sort()
return p[k - 1]
def main():
data = sys.stdin.buffer.read().split()
n, m, k = int(data[0]), int(data[1]), int(data[2])
a = [int(x) for x in data[3:3 + n]]
b = [int(x) for x in data[3 + n:3 + n + m]]
print(Solution().kthSmallestProduct(a, b, k))
main()Cách 2Chặt nhị phân đáp án + đếm số cặp – O(n log m log V)
Ý tưởng: đoán đáp án rồi đếm
Phương pháp giải của mình là Binary Search (tìm kiếm nhị phân) theo kết quả. Đầu tiên ta sắp xếp dãy $a$ tăng dần, dãy $b$ tăng dần theo giá trị (đề cho sẵn rồi, nhưng code mình vẫn sort cho chắc). Ta chia dãy $a$ thành 2 dãy: nega là danh sách các số âm của dãy $a$, posa là danh sách các số $\ge 0$ của dãy $a$.
Với mỗi giá trị $v$, ta đếm số lượng cặp $(i, j)$ sao cho $a[i] \cdot b[j] \le v$, gọi là $cnt(v)$. Nếu $cnt(v) \ge K$, ta sẽ chấp nhận $v$ làm đáp án, tuy nhiên vẫn có thể tồn tại số $v$ nhỏ hơn cũng thoả. Khi $v$ tăng thì $cnt(v)$ chỉ có tăng (hoặc giữ nguyên), nên đáp án chính là số $v$ nhỏ nhất mà $cnt(v) \ge K$ ⇒ tìm kiếm nhị phân được.
Tích $a[i] \cdot b[j]$ nằm trong đoạn $[-10^{10}, 10^{10}]$ (vì $|a[i]|, |b[j]| \le 10^5$), nên ta đặt lo $\approx -10^{10}$, hi $\approx 10^{10}$, lấy mid = (lo + hi) / 2. Ta đếm số lượng cặp $(i, j)$ có tích $\le$ mid, so sánh với $K$: nếu $\ge K$ thì ghi nhận ans = mid và tìm tiếp bên trái (hi = mid - 1), ngược lại tìm bên phải (lo = mid + 1). Đoạn tìm kiếm dài cỡ $2 \cdot 10^{10}$ nên chỉ mất khoảng $\log_2(2 \cdot 10^{10}) \approx 35$ vòng lặp.
Đếm số cặp có tích ≤ v
Vấn đề cuối cùng là làm sao để đếm được số lượng cặp $(i, j)$? Xét bất đẳng thức $a[i] \cdot b[j] \le v$. Nếu ta cố định giá trị $a[i]$, ta chỉ cần đếm số lượng $j$ sao cho $a[i] \cdot b[j] \le v$. Có 3 trường hợp xảy ra:
- $a[i] = 0$: bất đẳng thức trở thành $0 \le v$. Do đó nếu $v \ge 0$, tất cả $m$ giá trị $j$ đều thoả. Nếu $v \lt 0$, không có giá trị $j$ nào thoả.
- $a[i] \lt 0$: chia hai vế cho số âm thì đổi chiều: $a[i] \cdot b[j] \le v \Leftrightarrow b[j] \ge \dfrac{v}{a[i]}$. Ta cần đếm số vị trí $j$ thoả $b[j] \ge v / a[i]$. Vì $b$ đã được sắp xếp, ta tìm vị trí $p$ nhỏ nhất sao cho $b[p] \ge v / a[i]$, số lượng vị trí $j$ thoả mãn là $m - p$ (đánh số từ 0). Đây là hàm
findBigger. - $a[i] \gt 0$: $a[i] \cdot b[j] \le v \Leftrightarrow b[j] \le \dfrac{v}{a[i]}$. Ta tìm vị trí $p$ lớn nhất sao cho $b[p] \le v / a[i]$, số lượng vị trí $j$ thoả mãn là $p + 1$. Đây là hàm
findSmaller.
Minh hoạ
Em nhập 2 mảng và $k$, rồi bấm Tiếp. Mỗi bước là một lần thử mid: bảng tô xanh các ô có tích $\le$ mid, cột bên phải là số ô xanh của từng hàng (đúng bằng kết quả của findSmaller / findBigger). Để minh hoạ gọn, mình cho lo, hi bắt đầu từ tích nhỏ nhất và lớn nhất (code thật dùng $\pm 10^{10}$, chỉ tốn thêm vài vòng):
Source code để các bạn tham khảo nếu làm theo hướng này (code C++ của mình đã AC trên LeetCode):
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findSmaller(const vector <int> &a, double x) {
int lo = 0;
int hi = (int) a.size() - 1;
int pos = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (1.0 * a[mid] <= x) {
pos = mid;
lo = mid + 1;
}
else {
hi = mid - 1;
}
}
return pos + 1;
}
int findBigger(const vector <int> &a, double x) {
int n = (int) a.size();
int lo = 0;
int hi = (int) n - 1;
int pos = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (1.0 * a[mid] >= x) {
pos = mid;
hi = mid - 1;
}
else {
lo = mid + 1;
}
}
if (pos == -1) {
return 0;
}
else {
return n - pos;
}
}
long long kthSmallestProduct(vector<int>& a, vector<int>& b, long long k) {
sort(a.begin(), a.end());
sort(b.begin(), b.end());
vector <int> nega, posa;
int n = (int) a.size();
int m = (int) b.size();
for (int i = 0; i < n; i++) {
if (a[i] >= 0) {
posa.push_back(a[i]);
}
else {
nega.push_back(a[i]);
}
}
long long ans = 0LL;
long long lo = -10000000007LL;
long long hi = 10000000007LL;
while (lo <= hi) {
long long mid = (lo + hi) >> 1;
long long total = 0LL;
for (int i = 0; i < (int) nega.size(); i++) {
double x = 1.0 * mid / nega[i];
total += findBigger(b, x);
}
for (int i = 0; i < (int) posa.size(); i++) {
if (posa[i] == 0) {
if (mid >= 0) {
total += m;
}
continue;
}
double x = 1.0 * mid / posa[i];
total += findSmaller(b, x);
}
if (total >= k) {
ans = mid;
hi = mid - 1;
}
else {
lo = mid + 1;
}
}
return ans;
}
};
int main() {
int n, m;
long long k;
cin >> n >> m >> k;
vector<int> a(n), b(m);
for (int i = 0; i < n; i++) cin >> a[i];
for (int j = 0; j < m; j++) cin >> b[j];
Solution sol;
cout << sol.kthSmallestProduct(a, b, k);
return 0;
}import sys
from bisect import bisect_left, bisect_right
from typing import List
class Solution:
def kthSmallestProduct(self, a: List[int], b: List[int], k: int) -> int:
a.sort()
b.sort()
m = len(b)
nega = [x for x in a if x < 0]
posa = [x for x in a if x >= 0]
ans = 0
lo, hi = -10000000007, 10000000007
while lo <= hi:
mid = (lo + hi) >> 1
total = 0
for x in nega: # x < 0: cần b[j] >= mid / x
c = -(-mid // x) # c = ceil(mid / x), chia nguyên chính xác
total += m - bisect_left(b, c)
for x in posa:
if x == 0: # 0 * b[j] = 0 <= mid khi mid >= 0
if mid >= 0:
total += m
continue
total += bisect_right(b, mid // x) # x > 0: cần b[j] <= floor(mid / x)
if total >= k:
ans = mid
hi = mid - 1
else:
lo = mid + 1
return ans
def main():
data = sys.stdin.buffer.read().split()
n, m, k = int(data[0]), int(data[1]), int(data[2])
a = [int(x) for x in data[3:3 + n]]
b = [int(x) for x in data[3 + n:3 + n + m]]
print(Solution().kthSmallestProduct(a, b, k))
main()double. Cách này an toàn ở bài này: $|mid| \le 10^{10}$ biểu diễn chính xác được bằng double, và nếu $mid / a[i]$ không nguyên thì nó cách số nguyên gần nhất ít nhất $1 / |a[i]| \ge 10^{-5}$, lớn hơn rất nhiều so với sai số làm tròn (cỡ $10^{-6}$) ⇒ phép so sánh luôn đúng. Bản Python thì mình dùng chia nguyên cho chắc ăn: với $a[i] \gt 0$ đếm $b[j] \le \lfloor mid / a[i] \rfloor$ (bisect_right), với $a[i] \lt 0$ đếm $b[j] \ge \lceil mid / a[i] \rceil$ (bisect_left), trong đó $\lceil x / y \rceil$ viết là -(-x // y).int. Vì vậy trong code lo, hi, mid, total, ans đều là long long và đoạn tìm kiếm là $[-10^{10} - 7,\ 10^{10} + 7]$.Đánh giá độ phức tạp của cách làm này:
- Không gian: chỉ thêm 2 mảng
nega,posa⇒ $O(n)$ (không tính 2 mảng đầu vào). - Thời gian: sắp xếp mất $O(n \log n + m \log m)$. Chặt nhị phân đáp án chạy khoảng $\log_2 V \approx 35$ vòng ($V \approx 2 \cdot 10^{10}$ là độ dài đoạn tìm kiếm), mỗi vòng duyệt $n$ phần tử của $a$, mỗi phần tử chặt nhị phân trên $b$ mất $O(\log m)$ ⇒ tổng cộng $O(n \cdot \log m \cdot \log V)$, cỡ $35 \cdot 5 \cdot 10^4 \cdot 16 \approx 2{,}8 \cdot 10^7$ phép tính.
nums1, nums2 không làm thay đổi tập các tích), hoặc thay chặt nhị phân trong bằng hai con trỏ để đếm trong $O(n + m)$ mỗi vòng. Với giới hạn đề bài thì code ở trên đã đủ AC rồi nha.negb, posb khai báo mà không dùng tới.- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét