Mô tả
Trung tâm khí tượng Bình Thuận đặt hai trạm đo nhiệt độ: một trạm ở trung tâm Phan Thiết và một trạm ở khu du lịch Mũi Né. Hai trạm này cách nhau chưa đầy hai mươi cây số nhưng vì địa hình và hướng gió mà nhiệt độ thường chênh lệch đôi chút. Kỹ sư viên muốn tìm ra khoảng thời gian mà hai trạm ghi nhận mức nhiệt gần nhau nhất, nhằm chứng minh microclimate hai nơi đang dần đồng nhất.
Cụ thể, bạn được cho hai danh sách nhiệt độ. Danh sách thứ nhất ghi các mức nhiệt (độ C, có thể âm) mà trạm Phan Thiết đo được trong nhiều ngày. Danh sách thứ hai ghi tương ứng cho trạm Mũi Né. Nhiệm vụ của bạn là chọn một mức nhiệt từ danh sách Phan Thiết và một mức nhiệt từ danh sách Mũi Né sao cho trị tuyệt đối của hiệu hai mức nhiệt đó là nhỏ nhất có thể, rồi trả về chính giá trị nhỏ nhất ấy.
Đầu vào
Hàm nhận hai tham số:
phanThiet: danh sách số nguyên (nhiệt độ trạm Phan Thiết).muiNe: danh sách số nguyên (nhiệt độ trạm Mũi Né).
Giới hạn: 1 ≤ độ dài mỗi danh sách ≤ 10^5, −10^9 ≤ mỗi phần tử ≤ 10^9.
Đầu ra
Trả về một số nguyên không âm là chênh lệch nhiệt độ nhỏ nhất giữa một phần tử của phanThiet và một phần tử của muiNe.
Ràng buộc
- Độ dài mỗi danh sách từ 1 đến 10^5.
- Trị tuyệt đối mỗi phần tử không vượt 10^9.
- Độ phức tạp thời gian mục tiêu: O((n+m) log(n+m)) hoặc tốt hơn, với n, m lần lượt là số phần tử hai danh sách.
Ví dụ
Giả sử phanThiet = [32, 28, 35, 30] và muiNe = [29, 33, 38].
Bước 1: sắp xếp Phan Thiết tăng dần thành [28, 30, 32, 35]. Bước 2: sắp xếp Mũi Né tăng dần thành [29, 33, 38]. Bước 3: dùng hai con trỏ quét hai dãy:
- So 28 và 29: lệch 1, tốt nhất hiện tại.
- Tăng con trỏ Phan Thiết lên 30: 30 với 29 lệch 1, vẫn 1.
- Tăng tiếp lên 32: 32 với 29 lệch 3, nên tăng con trỏ Mũi Né lên 33: 32 với 33 lệch 1.
- Tiếp tục đến khi hết, không cặp nào lệch dưới 1.
Vậy đáp án là 1.