这个问题有 2 个变体。
给定 2 个整数数组,从每个数组中选择单个元素,使它们的总和与给定整数值 V 的距离(数值上)最小。总和可以大于 V。
给定 3 个整数数组,从每个数组中选择单个元素,使它们的总和与给定整数值 V 的距离(数值上)最小。总和可以大于 V。
我知道分别有一个天真的 O(n^2) 和 O(n^3) 解决方案,我想问一下是否有任何优化运行时间的方法。
最佳答案
对于第一种情况,您可以对 O(nlogn)
中的两个数组进行排序,然后对于第一个数组中的每个元素 x
,找到 V-x
在第二个数组中使用二进制搜索/上限算法。
它的总复杂度仍然是 O(nlogn)
,小于 O(n*n)
。
对于第二种情况,您可以应用具有O(n*n*log(n))
复杂度的类似算法。
关于arrays - 查找总和与给定值的距离最小的对/三元组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55841970/