2

你得到三个排序的数组（按升序排列），你需要找到一个三元组（每个数组中的一个元素），使得距离最小。距离定义如下：如果a[i], b[j]和c[k]是三个元素，那么

distance = max{abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k])}

请给出 O(n) 时间复杂度的解决方案

4

2 回答 2

4

线性时间算法：

double MinimalDistance(double[] A, double[] B, double[] C)
{
    int i,j,k = 0;
    double min_value = infinity;
    double current_val;
    int opt_indexes[3] = {0, 0, 0);

    while(i < A.size || j < B.size || k < C.size)
    {
         current_val = calculate_distance(A[i],B[j],C[k]);
         if(current_val < min_value)
         {
               min_value = current_val;
               opt_indexes[1] = i;
               opt_indexes[2] = j;
               opt_indexes[3] = k;
         }    

         if(A[i] < B[j] && A[i] < C[k] && i < A.size)
             i++;
         else if (B[j] < C[k] && j < B.size)
             j++;
         else
             k++; 
    }

    return min_value;
}

在每一步中，您检查当前距离，然后将当前指向最小值的数组的索引递增。每个数组只迭代一次，这意味着运行时间是O(A.size + B.size + C.size).

如果您想要最佳索引而不是最小值，则可以返回opt_indexes而不是min_value.

于 2013-10-18T12:42:34.087 回答
1

假设我们只有一个排序数组，那么 3 个可能距离较小的连续元素是所需的解决方案。现在当我们有三个数组时，只需将它们全部合并并制作一个大的排序数组 ABC（这可以通过合并排序中的合并操作在 O(n) 中完成），只需保留一个标志来确定哪个元素属于哪个原始数组. 现在你必须像这样在数组中找到三个连续的元素：

a1,a2,b1,b2,b3,c1,b4,c2,c3,c4,b5,b6,a3,a4,a5,....

这里连续意味着它们按连续顺序属于 3 个不同的组，例如：a2,b3,c1 或 c4,b6,a3。

现在找到这棵树元素并不难，确保最小和最大的元素应该是某个三元组中第一个和最后一个组的元素的最后一个和第一个，例如在组中：[c2,c3,c4],[b5,b6]， [a3,a4,a5]，我们不需要检查a4,a5,c2,c3清楚这种情况下可能的解决方案是在 c4,[b5,b6],a5 之间，我们也不需要将 c4 与 b5,b6 进行比较，或者a5 与 b5，b6，确定距离由 a5-c4（在本组中）。所以我们可以从左边开始跟踪最后一个元素，并在每次迭代中更新最佳可能的解决方案，只需保留每个组的最后访问值。

示例（首先我应该说我没有编写代码，因为我认为这是 OP 的任务而不是我）：

假设我们在排序数组之后有这个序列：

a1,a2,b1,b2,b3,c1,b4,c2,c3,c4,b5,b6,a3,a4,a5,....

让我们一步一步迭代：

我们只需要跟踪数组中每个项目的最后一项，a用于跟踪当前最佳 a_i、b 用于 b_i 和 c 用于 c_i。假设一开始a_i=b_i=c_i=-1，

在第一步中a将是a1，在下一步中

a=a2,b=-1,c=-1
a=a2,b=b1,c=-1
a=a2,b=b2,c=-1
a=a2,b=b3,c=-1,
a=a2,b=b3,c=c1,

此时我们将当前指针 (a2,b3,c1) 保存为差异的最佳值，

在下一步中：

a=a2,c=c1,b=b4

现在我们将 b4-a2 与之前最佳选项的差异进行比较，如果更好，我们将这个指针保存为现在的解决方案，然后继续：

a=a2,b=b4,c=c2 (again compare and if needed update the best solution),
a=a2,b=b4,c=c3 (again ....)
a=a2,b=b4,c=c4 (again ....)
a=a2, b=b5,c=c4, ....

好的，如果从文本中不清楚，合并后我们有（我假设所有数组至少有一个元素）：

解决方案=无限；a=b=c=-1，最佳A=最佳B=最佳C=1；

for (int i=0;i<ABC.Length;i++)
{
    if(ABC[i].type == "a") // type is a flag determines 
                           // who is the owner of this element
    {
        a=ABC[i].Value; 
        if (b!=-1&&c!=-1)
        {
          if (max(|a-b|,|b-c|,|a-c|) < solution)
          {
            solution =  max(|a-b|,|b-c|,|a-c|);
            bestA= a,bestB = b,bestC = c;
          }
        }
    }
    // and two more if for type "b" and "c"
}

当然还有比这更优雅的算法，但我看到你的链接有问题，所以我想这种看待问题的简单方法会更容易，之后你就可以理解你自己的链接。

于 2013-10-18T12:43:30.877 回答