Giả sử chúng ta có ba mảng đã sắp xếp A, B, C và ba phần tử i, j, k lần lượt từ A, B, C sao cho max(|A[i] – B[j]|, |B[j] – C[k]|, |C[k] – A[i]|) được tối thiểu hóa. Ví dụ A = [1, 4, 10], B = [2, 15, 20], C = [10, 12], thì các phần tử đầu ra là 10, 15, 10.
Giả sử kích thước của A, B, C lần lượt là p, q, r. Các bước giải quyết:
- i := 0, j := 0, k := 0
- Thực hiện while i < p và j < q và k < r:
- Tìm min và max của A[i], B[j], C[k]
- Tính diff := max - min
- Nếu diff nhỏ hơn kết quả hiện tại, cập nhật kết quả
- Tăng con trỏ của mảng chứa giá trị min.
Ví dụ
#include <iostream> using namespace std; void getClosestElements(int A[], int B[], int C[], int p, int q, int r) { int diff = INT_MAX; int i_final =0, j_final = 0, k_final = 0; int i=0,j=0,k=0; while (i < p && j < q && k < r) { int min_element = min(A[i], min(B[j], C[k])); int max_element = max(A[i], max(B[j], C[k])); if (max_element-min_element < diff){ i_final = i, j_final = j, k_final = k; diff = max_element - min_element; } if (diff == 0) break; if (A[i] == min_element) i++; else if (B[j] == min_element) j++; else k++; } cout << A[i_final] << " " << B[j_final] << " " << C[k_final]; } int main() { int A[] = {1, 4, 10}; int B[] = {2, 15, 20}; int C[] = {10, 12}; int p = sizeof A / sizeof A[0]; int q = sizeof B / sizeof B[0]; int r = sizeof C / sizeof C[0]; cout << "Closest elements are: "; getClosestElements(A, B, C, p, q, r); }
Kết quả
Closest elements are: 10 15 10