資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究最小化三個不同已排序陣列中 (max(A[i], B[j], C[k]) – min(A[i], B[j], C[k])) 的C++實現
概念
對於給定的三個已排序陣列 A、B 和 C（大小不一定相同），計算任何三元組 A[i]、B[j]、C[k]（分別屬於陣列 A、B 和 C）的最大值和最小值之間的最小絕對差，即最小化 (max(A[i], B[j], C[k]) – min(A[i], B[j], C[k]))。
輸入−
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
輸入−
A = [ 6, 9, 11, 16 ] B = [ 7, 10, 16, 79, 90 ] C = [ 3, 4, 7, 7, 9, 9, 11 ]
輸出−
1
解釋−
當我們選擇 A[i] = 11，B[j] = 10，C[k] = 11 時，我們得到最小差值為 max(A[i], B[j], C[k]) - min(A[i], B[j], C[k])) = |11-10| = 1
方法
從陣列 A、B 和 C 中最大的元素開始。跟蹤一個變數，以便在執行每個步驟時更新答案。
在每一步中，減小差值的唯一方法是減小三個元素中的最大元素。
因此，訪問包含此步驟中最大元素的陣列中的下一個最大元素，並更新答案變數。
我們必須重複此步驟，直到包含最大元素的陣列結束。
示例（C++）
// 以上方法的 C++ 程式碼
#include<bits/stdc++.h>
usingnamespacestd;
intsolve(intA1[], intB1[], intC1[], inti1, intj1, intk1) {
intmin_diff, current_diff, max_term;
// calculating min difference from last
// index of lists
min_diff = abs(max(A1[i1], max(B1[j1], C1[k1]))
- min(A1[i1], min(B1[j1], C1[k1])));
while(i1 != -1 && j1 != -1 && k1 != -1) {
current_diff = abs(max(A1[i1], max(B1[j1], C1[k1]))
- min(A1[i1], min(B1[j1], C1[k1])));
// checking condition
if(current_diff < min_diff)
min_diff = current_diff;
// calculating max term from list
max_term = max(A1[i1], max(B1[j1], C1[k1]));
if(A1[i1] == max_term)
i1 -= 1;
elseif(B1[j1] == max_term)
j1 -= 1;
else
k1 -= 1;
}
returnmin_diff;
}
intmain() {
intD1[] = { 5, 8, 10, 15 };
intE1[] = { 6, 9, 15, 78, 89 };
intF1[] = { 2, 3, 6, 6, 8, 8, 10 };
intnD = sizeof(D1) / sizeof(D1[0]);
intnE = sizeof(E1) / sizeof(E1[0]);
intnF = sizeof(F1) / sizeof(F1[0]);
cout << solve(D1, E1, F1, nD-1, nE-1, nF-1);
return0;
}輸出
1
更新於：2020年8月27日
324 次瀏覽
廣告