分而治之算法

Question

几周前我参加了一个求职面试，我被要求设计一个分而治之的算法。我无法解决这个问题，但他们刚刚打电话给我进行第二次面试！下面是问题：

我们给出两个整数的n元数组A0..n 0..n − 1−1和B0..n − 1，以及一个整数值作为输入。给出一个O(nlogn)分治算法，该算法确定是否存在不同的值i，j(即i != j)使得Ai + Bj = value。如果i，j存在，你的算法应该返回True，否则返回False。你可以假设A中的元素是不同的，B中的元素也是不同的。

有人能解决这个问题吗？谢谢

Answer 1

以下算法不使用Divide and Conquer，但它是解决方案之一。您需要对这两个数组进行排序，维护元素的索引可能会对成对的数组进行排序(elem, index)。这会占用O(n log n)时间。

然后，您可以应用合并算法来检查是否存在两个Ai+Bj = value的元素。这将是O(n)

总体时间复杂度将为O(n log n)

Answer 2

我的方法是..

1. 对任意数组进行排序。在这里，我们对数组A进行排序，使用Merge Sort算法对B的每个元素进行Divide and Conquer algorithm.
2. Then排序，通过Binary Search在数组A中搜索Required Value- Element of B。这也是一种Divide and Conquer算法，如果你从数组A中找到元素
3. ，那么两个元素都会成对，使得Required Value - Element of B

出于时间复杂性的考虑，A有N元素，因此Merge Sort将获取O(N log N)，我们对B(共N个元素)中的每个元素执行Binary Search，B(共N个元素)将获取O(N log N)。所以总的时间复杂度是O(N log N)。

正如你已经提到的，你需要检查i != j，如果是A[i] + B[j] = value，那么在这里你可以接受大小为N * 2的2D数组。每个元素与其原始索引配对，作为每行的第二个元素。排序将根据存储在第一个元素中的数据进行。然后，当您找到元素时，您可以比较两个元素的原始索引，并相应地返回值。

Answer 3

我建议使用散列。即使这不是你应该用来解决问题的方法，但值得一提的是，哈希算法的时间复杂度要比O(n)和O(n*log(n))更好，这就是为什么它更高效的原因。

1. 将A转换为哈希集(如果我们想要i索引，则将其转换为字典)- O(n)
2. Scan B并检查哈希集(字典)中是否有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");