分而治之算法

Question

幾周前我有一次求職面試，我被要求設計一個分而治之算法。我無法解決問題，但他們只是打電話給我第二次面試！這裏是一個問題：我們給出了兩個n元素數組A [0..n-1]和B [0..n-1]（其中 不一定是整數），一個整數值。給出一個O（nlogn）分而治之算法，它確定是否存在不同的值i，j（即i！= j），使得A [i] + B [j] =值。如果i，j存在，那麼你的算法應該返回True，否則返回False。你可以假設A中的元素是不同的，而B中的元素是不同的。

任何人都可以解決這個問題嗎？謝謝

Answer 1

下面的算法不使用分而治之，但它是解決方案之一。 您需要對兩個數組進行排序，並維護元素的索引，以排序(elem, index)對的數組。這需要O(n log n)時間。

然後，您可以應用合併算法來檢查是否存在兩個元素，例如A [i] + B [j] = value。這將O(n)

總體時間複雜度將是O(n log n)

Answer 2

我的做法是..

1. 排序任意陣列。這裏我們對數組A進行排序。使用算法對其進行排序，該算法是Divide and Conquer算法。
2. 然後對於B的每個元素，通過Binary Search在數組A中搜索Required Value- Element of B。這又是一個Divide and Conquer算法。
3. 如果您從數組A中找到元素Required Value - Element of B，那麼Both元素使得對的數目爲Element of A + Element of B = Required Value。

所以這裏的時間複雜度，A有N元素，因此Merge Sort將採取O(N log N)和我們爲這需要O(N log N) B的每一個元素（總氮元素）做Binary Search。所以總的時間複雜度將是O(N log N)。

正如你所說的，你需要檢查i != j如果A[i] + B[j] = value然後在這裏你可以採取二維數組的大小N * 2。每個元素都與其原始索引配對，作爲每行的第二個元素。根據存儲在第一個元素中的數據完成排序。然後，當您找到元素時，您可以比較兩個元素的原始索引並相應地返回值。

Answer 3

我建議使用哈希。即使它是而不是你應該解決這個問題，值得一提的是，哈希算法具有更好的時間複雜度O(n) v。O(n*log(n))這就是爲什麼更高效。

1. 打開A成HashSet的（或字典如果我們想i指數） - O(n)
2. 掃描B並檢查是否有在HashSet中的value - B[j]（字典） - O(n)

所以你有一個O(n) + O(n) = O(n)算法（這是更好需要(O n * log(n))，然而，該解決方案是不分而治之）：

樣品C＃實現

int[] A = new int[] { 7, 9, 5, 3, 47, 89, 1 }; 
    int[] B = new int[] { 5, 7, 3, 4, 21, 59, 0 }; 

    int value = 106; // 47 + 59 = A[4] + B[5] 

    // Turn A into a dictionary: key = item's value; value = item's key 
    var dict = A 
    .Select((val, index) => new { 
     v = val, 
     i = index, }) 
    .ToDictionary(item => item.v, item => item.i); 

    int i = -1; 
    int j = -1; 

    // Scan B array 
    for (int k = 0; k < B.Length; ++k) { 
    if (dict.TryGetValue(value - B[k], out i)) { 
     // Solution found: {i, j} 
     j = k; 

     // if you want any solution then break 
     break; 

     // scan further (comment out "break") if you want all pairs 
    } 
    } 

    Console.Write(j >= 0 ? $"{i} {j}" : "No solution"); 

Answer 4

似乎很難做到不排序。

如果離開排序，則列，檢查的A[i]+B[j] = Value存在需要時間Ω(n)固定i，然後檢查所有i需要Θ(n²)，除非你找到一招把一些秩序B。

平衡鴻溝似乎&征服的無序排列並沒有任何好轉：如果您在兩半分A和B，該解決方案能夠橫亙在Al/Bl一個，Al/Br，Ar/Bl，Ar/Br這產生復發T(n) = 4 T(n/2)，它有一個二次方案。

如果允許排序，Sanket Makani提供的解決方案是一種可能性，但您在搜索階段的時間複雜性方面做得更好。

事實上，假設A和B現在排序，並考慮2D功能A[i]+B[j]，這是在兩個方向上i和j單調。然後，域A[i]+B[j] ≤ Value受單調曲線j = f(i)或等同於i = g(j)的限制。但是對於曲線的所有點必須嚴格檢查嚴格的相等性A[i]+B[j] = Value，並且在最壞的情況下無法避免在任何地方評估f。

從i = 0開始，通過二分搜索獲得f(i)。然後，您可以逐漸跟隨邊界曲線。您將沿着i方向執行n步驟，並且在j方向中最多執行n步驟，因此複雜度仍以最優的O(n)爲界。

下面是一個示例，顯示總和低於和高於目標值的區域（有兩個匹配項）。

這個最佳的解決方案有什麼與鴻溝&征服。也許可以根據對中心點求和的評估來設計一個變體，這樣就可以丟棄整個象限，但這是非常人造的。