附近的三个号码中三个数组 [英] Three nearby numbers in three arrays

问题描述

鉴于3排序浮点数组a []，B []，和c []，设计一种linearithmic算法找到三个整数I，J，和k，使得| A [1] - B [j]的| + | B [J] - C [K] | + | C [K] - A [1] |最小。

Given three sorted floating-point arrays a[], b[], and c[], design a linearithmic algorithm to find three integers i, j, and k such that |a[i] - b[j]| + |b[j] - c[k]| + |c[k] - a[i]| is minimum.

我心里有一个解决方案，但我不认为这是linearithmic。这就是我现在所拥有的：

I do have a solution in mind but I don't think that is linearithmic. This is what I have right now:

 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

首先，我想知道是否有更好的解决办法？如果没有，那么我我就在想，这个解决方案没有linearithmic的复杂性？最近的数字可以用二进制搜索找到。

First of all, I'd like to know if there is any better solution? If not, then am I right in thinking that this solution doesn't have linearithmic complexity? The closest number can be found using binary search.

现在的问题是，从算法 - 第4版由罗伯特·塞奇威克和凯文·韦恩和我preparing为即将到来的面试。

The question is from "Algorithms - 4th Ed." by Robert Sedgewick and Kevin Wayne and I'm preparing for an upcoming interview.

有些类似的问题：<一href="http://stackoverflow.com/questions/10005929/match-three-or-more-nearest-numbers-from-arrays">Match三个或三个以上的阵列最近数

推荐答案

让我们来看看一些潜在的因素排序：

Let us look at some potential ordering of the elements:

a[i] < b[j] < c[k]

然后，我们可以看到下面的索赔成立：

Then we can see the following claim holds:

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 ）的在你给一个引用（可以在linearithmic时间为每一对来完成）。

So, for any possible ordering, this is the minimization of the difference between two elements in two different arrays. So, simply minimize for every possible combination (a and b, b and c, c and a) as shown in the question you gave a reference to (can be done in linearithmic time for each pair).

一旦你找到了最小的一对，发现从第三排匹配的元素应该是很容易 - 只需进入了数组，并检查每个元素

Once you found the minimization for a pair, finding the matching element from the third array should be quite easy - simply go over that array and check each element.

这篇关于附近的三个号码中三个数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！