algorithm - 有没有更快的方法找到 "lucky triples"的数量？

Question

我正在研究一个代码挑战问题——“找到幸运的三元组”。 “幸运三元组”定义为“在列表 lst 中，对于像 (lst[i], lst[j], lst[k]) where i < j < k 这样的三元组的任意组合，其中 lst[i] divides lst[j] 和 lst[j] divides lst[k]。

我的任务是找出给定列表中幸运三元组的数量。蛮力方法是使用三个循环，但解决问题需要花费太多时间。我写了这个，系统响应“超时”。这些问题看起来愚蠢而简单，但数组未排序，因此二分查找等一般方法不起作用。我被这个问题惊呆了一天，希望有人能给我一个提示。我正在寻求一种更快地解决问题的方法，至少时间复杂度应该低于 O(N^3)。

Answer 1

一个简单的类似动态规划的算法将在二次时间和线性空间中执行此操作。你只需要维护一个计数器 c[i]对于列表中的每个项目，它表示将 L[i] 整除的先前整数的数量.

然后，当您浏览列表并测试每个整数时 L[k]与所有之前的项目 L[j] , 如果 L[j]划分 L[k] ，您只需添加 c[j] (可能是 0)到你的三元组的全局计数器，因为这也意味着恰好存在 c[j]项目 L[i]这样 L[i]划分 L[j]和 i < j .

int c[] = {0}
int nbTriples = 0
for k=0 to n-1
  for j=0 to k-1
    if (L[k] % L[j] == 0)
      c[k]++
      nbTriples += c[j]
return nbTriples

可能有一些更好的算法使用奇特的离散数学来更快地完成它，但如果 O(n^2) 没问题，这就可以了。

关于您的评论:

• 为什么是 DP？我们有一些东西可以清楚地建模为具有从左到右的顺序(DP 橙色标志)，感觉就像重用以前计算的值可能会很有趣，因为蛮力算法会多次执行完全相同的计算。

• 如何从中得出解决方案？运行一个简单的示例(提示:最好从左到右处理输入)。在步骤i ，计算你可以从这个特定点计算出的东西(忽略 i 右边的所有东西)，并尝试针对不同的 i's 一遍又一遍地查明你计算的东西。 : 这是你想要缓存的。在这里，当您在 k 步看到一个潜在的三元组时( L[k] % L[j] == 0 )，你必须考虑 L[j] 上会发生什么:“它的左边是否也有一些除数？每一个都会给我们一个新的三元组。让我们看看......但是等等!我们已经在步骤 j 中计算了它!让我们缓存这个值!”这就是你跳到座位上的时候。