3個數組情況下的代碼複雜度

Question

給出三個排序數組（按升序排列），您需要找到一個三元組（每個數組中的一個元素），使距離最小。 距離被定義如下： 如果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）的時間複雜度的溶液

Answer 1

線性時間算法：

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。

Answer 2

假設我們只有一個排序數組，那麼3個連續元素的距離較小是所需的解決方案。現在，當我們有三個數組時，將它們全部合併並創建一個大的排序數組ABC（這可以通過merge-sort中的合併操作在O（n）中完成），只需保留一個標誌以確定哪個元素屬於哪個原始數組。現在，你必須找到在陣列連續三個要素是這樣的：

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

，在這裏連續的手段，他們屬於3個不同的組連續的順序，e.g：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組成（在該組中）。所以我們可以從左邊開始，跟蹤最後一個元素，並通過保持每個組的最後訪問值來更新每個迭代中最好的解決方案。

例（第一我應該說，我沒有寫的代碼，因爲我覺得這是O​​P的任務不是我）：

假設我們有一個排序的數組後，此序列：

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，

一個將是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， bestA = bestB = bestC = 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" 
} 

肯定有更優雅的算法比這個，但我看到你有問題，你的鏈接，所以我想的看問題這個簡單的方式使得它更容易，以後你可以瞭解自己的鏈接。