-
Ý tưởng: Xét
$f(x) = |x + a|$ . Ta thấy$f(x)$ đạt giá trị nhỏ nhất khi$x = -a$ . Do đó, với mỗi$a_i$ , ta tìm phần tử$b_j$ gần với$-a_i$ nhất. -
Cài đặt:
- Để việc tìm kiếm được hiệu quả, ta có thể sắp xếp lại
$B$ và dùng tìm kiếm nhị phân. Cụ thể, với$a_i$ , ta tìm kiếm$b_j$ là lower bound của$-a_i$ . Khi đó có 2 "ứng cử viên" là$j - 1$ (nếu$j > 0$ ) và$j$ . -
Optional: Thay vì chọn cố định
$B$ là mảng được sắp xếp và tìm kiếm trên đó, ta có thể chọn mảng nhỏ hơn.
- Để việc tìm kiếm được hiệu quả, ta có thể sắp xếp lại
-
Độ phức tạp:
$O((m + n) \log n)$ - Sắp xếp
$B$ :$O(n \log n)$ . - Duyệt qua từng phần tử của
$A$ và tìm kiếm nhị phân tương ứng trên$B$ :$O(m \times \log n)$ . - Nếu ta chọn mảng nhỏ hơn là mảng để sắp xếp và tìm kiếm, thì độ phức tạp sẽ là
$O((m + n) \log (\min {m, n}))$ .
- Sắp xếp