给定三个排序的浮点数组a[]，b[]和c[]，设计一个线性算法来找到三个整数i，j和k，使得|a[i] - b[j]| + |b[j] - c[k]| + |c[k] - a[i]|最小。
我确实有一个解决方案，但我不认为这是线性的。
assume minDiff = // some huge value
for each entry in 'a'
find an entry closest to it in 'b' and call it 'closestToA'
find an entry closest to 'closestToA' in 'c' and call it 'closestToB'
compute the diff:
int currDiff = Math.abs(a[i] - closestToA) + Math.abs(closestToA - closestToB) + Math.abs(closestToB - a[i]);
Replace minDiff with currDiff, if currDiff < minDiff
首先，我想知道是否有更好的解决方案？如果没有，那么我认为这个解决方案没有线性复杂性是正确的吗？使用二进制搜索可以找到最接近的数字。
问题来自“算法-第 4 版”。 · 塞奇威克和凯文 · 韦恩，我正在为即将到来的采访做准备。
让我们来看看一些潜在的元素排序：
a[i] < b[j] < c[k]
然后我们可以看到以下主张成立：
Target = |a[i] - b[j]| + |b[j] - c[k]| + |c[k] - a[i]|
= b[j] - a[i] + c[k] - b[j] + c[k] - a[i]
= 2 * (c[k] - a[i])
因此，对于任何可能的排序，这是两个不同数组中两个元素之间差异的最小化。因此，简单地最小化每个可能的组合（a和b，b和c，c和a），如您给出的每个线性对的问题所示。
一旦你找到了一对的最小化，从第三个数组中找到匹配的元素应该很容易-只需遍历该数组并检查每个元素。
下面的算法几乎就像将三个排序的数组合并成一个排序的数组。
为每个数组保留一个指针（i，j，k 分别为 A，B 和 C）。将它们初始化为 0。
然后计算 A [i] 、 B [j] 、 C [k] 之间的差,并且如果必要的话,更新到目前为止所实现的最低值。
递增数组中的索引
array[index] = min(A[i], B[j] and C[k])
如果它还没有到达终点。
That is:
If ( A[i] is the least ), then increment i.
else If ( B[j] is the least ), then increment j.
else increment k.
继续进行上述操作，直到任何一个索引超过末尾，或者您发现所有三个 A [i]，B [j] 和 C [k] 都相等的情况。
编辑：
如果有两个重复的候选人（说 A [i] = = B [j]），然后增加 i 和 j。
此外，如果 A [i + 1] = = A [i]，则只需再次递增 i。
结束编辑：
上述算法具有 O (N) 的时间复杂度。
正确性证明：
如其他答案所示，差异仅取决于 A [i]，B [j]，C [k] 的两个极端。
因此，如果 A [i] ＆ lt;B [j] ＆ lt;C [k]，则差 = 2 *（C [k]-A [i]）。因此，如果我们增加 j 或 k，则差只能增加。因此，我们增加 i。
本站系公益性非盈利分享网址，本文来自用户投稿，不代表边看边学立场，如若转载，请注明出处
评论列表（57条）