我需要帮助来优化上个月在采访中提出的数组问题。

Question

给定两个数组a和b，求出bi + bj + bk (i !=j = k)的最大值，其中满足ai > aj > ak的条件

我可以用三个循环来计算。我被要求在面试中优化这个问题，但没能做到。有比O(n^3)更好的优化方法吗？谢谢

Answer 1

您可能可以通过排序B (n日志n时间)和跟踪所使用的索引，检查A的属性A[i] > A[j] > A[k]，从而获得O(n log n)解决方案。请注意，由于i、j和k之间的唯一关系是它们不相等，所以它们的顺序似乎并不重要。(而且，可能i和k是相等的，但我们暂时忽略这一点。)

伪码：

function findSum(A, B):
  declare array B_with_index
 
  // O(n)
  for index 0 to |B|-1:
    insert (B[index], index) into B_with_index

  // O(n log n)
  sort B_with_index by its first value, descending

  // O(n)
  for index 0 to |B|-3:
    b_1 := B_with_index[index]
    b_2 := B_with_index[index+1]
    b_3 := B_with_index[index+2]

    // Note that we're only checking for inequality here
    // This is because i, j and k have no relationship
    // other than inequality. E.q., if A[i] < A[j], we can
    // just swap the definitions of i and j.
    if A[b_1.index] != A[b_2.index] and A[b_2.index] != A[b_3.index] then
      return b_1.value + b_2.value + b_3.value

  return error

这取决于这样一个事实，即如果对数组(如[1, 5, 25, 2, -5, 50] )进行排序，最大和将位于开头：[50, 25, 5, 2, 1, -5]。然后，您所要做的就是确保所涉及的索引在A中具有正确的属性。