Minimize max(A[i],B[j],C[k]) - min(A[i],B[j],C[k]) จาก 3 อาร์เรย์เรียงลำดับ
กำหนดอาร์เรย์ 3 ตัว A, B, C ที่เรียงจากน้อยไปมาก (ขนาดอาจต่างกัน) ต้องหา Triplet (a,b,c) ที่ทำให้ max(a,b,c) - min(a,b,c) น้อยที่สุด
ตัวอย่าง: A=[2,5,6,9,11], B=[7,10,16], C=[3,4,7,7] → เลือก 6,7,7 → ความต่าง = 1
อัลกอริทึม Three Pointers (O(N))
- เริ่มต้น pointer ทั้งสามที่ตำแหน่งสุดท้าย (ค่ามากสุด)
- คำนวณ
diff = max - minอัปเดตค่าน้อยสุด - ลด pointer ที่อยู่ที่ค่า
maxลง 1 (เพราะลดค่ามากสุดอาจลดช่องว่างได้) - ทำซ้ำจน pointer ใดถึง -1
โค้ดตัวอย่าง Python
def solve(A, B, C):
i, j, k = len(A)-1, len(B)-1, len(C)-1
min_diff = abs(max(A[i], B[j], C[k]) - min(A[i], B[j], C[k]))
while i >= 0 and j >= 0 and k >= 0:
cur_max = max(A[i], B[j], C[k])
cur_min = min(A[i], B[j], C[k])
min_diff = min(min_diff, cur_max - cur_min)
if A[i] == cur_max:
i -= 1
elif B[j] == cur_max:
j -= 1
else:
k -= 1
return min_diff
A = [2, 5, 6, 9, 11]
B = [7, 10, 16]
C = [3, 4, 7, 7]
print(solve(A, B, C)) # 1
