是否有有效的方法来降低这个问题的时间复杂度?电流T(n) = O(n ^3)

Question

需要选择的值使等式abs('a' - 'b') + abs('b' - 'c') + abs('c' - 'a')的值最小。

def minimumValue(n: int, a: List[int], b: List[int], c: List[int]) -> int :
# Write your code here.
ans=10000000000000
for i in range (n):
for j in range (n):
for k in range (n):
ans = min(ans, abs(a[i] - b[j]) + abs(b[j] - c[k]) + abs(c[k] - a[i]))

return ans

Answer 1

这是一个0 (nlogn)解。您可以对这三个列表进行排序，然后执行以下操作:

• 从三个列表中获取第一个值

• 当我们有三个值时重复:

  • 对这三个值进行排序(并跟踪它们的来源)
  • 用这三个计算目标表达式，并检查它是否比目前为止的最佳结果有所改善
  • 将这三个值中的最小值替换为与该值来自同一列表的下一个值。如果列表中没有下一个值，返回结果(quit)

还请注意，要计算的表达式的公式与计算(max(x,y,z)-min(x,y,z))*2的公式相同，当x,y和z的值排序时，这很容易做到，因为它变成了(z-x)*2。为了找到这个表达式可以取的最小值，我们可以省略*2，只在最后进行乘法运算。

下面是实现这个想法的代码:

def minimumValue(n: int, a: List[int], b: List[int], c: List[int]) -> int:
queues = map(iter, map(sorted, (a, b, c)))
three = [[next(q), q] for q in queues]
least = float("inf")
while True:
three.sort()    
least = min(least, three[2][0] - three[0][0])
try:
three[0][0] = next(three[0][1])
except:
return least*2

初始排序三个输入列表的时间复杂度为O(nlogn)。循环将迭代3n-2次，也就是O(n)。一个循环迭代中的每个动作在固定时间内执行。

所以总体复杂度由初始排序决定:O(nlogn)

Answer 2

在对这3个列表的内容没有任何进一步的了解/假设的情况下，如果您需要获得真正的最小值(而不是近近值)，那么除了使用蛮力之外别无选择。一些优化是可能的，但仍然有N^3的复杂度(在最坏的情况下没有任何加速)。

for i in range (n):
for j in range (n):
v = abs(a[i] - b[j])
if v < ans:
for k in range (n):
ans = min(ans, v + abs(b[j] - c[k]) + abs(c[k] - a[i]))