在三个向量的集合中找到最接近的三元组

Question

给定三个双向量，我想对每个向量中的每个元素进行配对，使每个三元组中最大和最小元素之间的差异最小化，并且每个向量的每个元素都是三元组的一部分。现在，我正在使用std::lower_bound():

double closest(vector<double> const& vec, double value){ auto const ret = std::lower_bound(vec.begin(), vec.end(), value); return(*ret); }
int main(){
vector<double> a, b, c; vector<vector<double>> triples;
for(auto x : a){
triples.push_back({x, closest(b, x), closest(c, x)});
}
}

假设这里的a、b和c填充了一些值。问题是，lower_bound()返回的最近元素不小于参数。我还想考虑不到论点的因素。有什么好方法吗？

Answer 1

我的解决方案是实现一个二进制搜索，以比较相邻元素结束。另一种可能的解决方案是迭代每个向量/数组的元素，根据需要调整索引以最小化差异(这可能与理想复杂度为$O(\log｛n｝($？的二进制搜索相比(：

int solve(int A[], int B[], int C[], int i, int j, int k) 
{  
int min_diff, current_diff, max_term; 

min_diff = Integer.MAX_VALUE; 

while (i != -1 && j != -1 && k != -1)  
{ 
current_diff = abs(max(A[i], max(B[j], C[k]))  
- min(A[i], min(B[j], C[k]))); 

if (current_diff < min_diff) 
min_diff = current_diff; 

max_term = max(A[i], max(B[j], C[k])); 
if (A[i] == max_term) 
i -= 1; 
else if (B[j] == max_term) 
j -= 1; 
else
k -= 1; 
} 

return min_diff; 
}