สมมติว่าเรามีอาร์เรย์ที่จัดเรียงอยู่สามชุด A, B และ C (อาจมีขนาดต่างกัน) เราต้องหาค่าความต่างสัมบูรณ์ขั้นต่ำระหว่างจำนวนสูงสุดและต่ำสุดของ triplet ใดๆ (A[i],B[j], C[k]) ให้อยู่ในอาร์เรย์ A, B และ C ตามลำดับ
ดังนั้น หากอินพุตเป็น A :[ 2, 5, 6, 9, 11 ], B :[ 7, 10, 16 ], C :[ 3, 4, 7, 7 ] ผลลัพธ์จะเป็น 1 เป็น โดยการเลือก A[i] =6 B[j] =7 และ C[k] =7 เราจะได้ค่าความแตกต่างขั้นต่ำเป็น max(A[i], B[j], C[k]) - min(A [i], B[j], C[k])) =|7-6| =1
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- i :=ขนาด A - 1
- j :=ขนาด B - 1
- k :=ขนาด C - 1
- minimum_dfference :=| สูงสุดของ A[i], B[j], C[k] - ค่าต่ำสุดของ A[i], B[j], C[k]|
- ในขณะที่ i ไม่เหมือนกับ -1 และ j ไม่เหมือนกับ -1 และ k ไม่เหมือนกับ -1 ให้ทำ
- current_diff :=| สูงสุดของ A[i], B[j], C[k] - ค่าต่ำสุดของ A[i], B[j], C[k]|
- ถ้า current_diff
- minimum_dfference :=current_diff
- maximum_term :=สูงสุดของ A[i], B[j], C[k]
- ถ้า A[i] เหมือนกับ maximum_term แล้ว
- i :=i - 1
- มิฉะนั้นเมื่อ B[j] เหมือนกับ maximum_term แล้ว
- j :=j - 1
- มิฉะนั้น
- k :=k - 1>
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def solve(A, B, C): i = len(A) - 1 j = len(B) - 1 k = len(C) - 1 minimum_dfference = abs(max(A[i], B[j], C[k]) - min(A[i], B[j], C[k])) while i != -1 and j != -1 and k != -1: current_diff = abs(max(A[i], B[j], C[k]) - min(A[i], B[j], C[k])) if current_diff < minimum_dfference: minimum_dfference = current_diff maximum_term = max(A[i], B[j], C[k]) if A[i] == maximum_term: i -= 1 elif B[j] == maximum_term: j -= 1 else: k -= 1 return minimum_dfference A = [ 2, 5, 6, 9, 11 ] B = [ 7, 10, 16 ] C = [ 3, 4, 7, 7 ] print(solve(A, B, C))
อินพุต
A = [ 2, 5, 6, 9, 11 ] B = [ 7, 10, 16 ] C = [ 3, 4, 7, 7 ]
ผลลัพธ์
1
