找到“幸运三元组”数量的更快方法？ [英] Any faster way to find the number of "lucky triples"?

问题描述

我正在研究代码挑战问题-找到幸运三元组。 幸运三元组被定义为在列表 lst 中，对于任何三元组的组合，如（lst [i]，lst [j]，lst [k]），其中i< j< k ，其中 lst [i]除以lst [j] 和 lst [j]除以lst [k] 。

I am working on a code challenge problem -- "find lucky triples". "Lucky triple" is defined as "In a list lst, for any combination of triple like (lst[i], lst[j], lst[k]) where i < j < k, where lst[i] divides lst[j] and lst[j] divides lst[k].

我的任务是找到给定列表中幸运三元组的数量。一种方法是使用三个循环，但是解决该问题花费了太多时间，我编写了这个循环，系统响应时间超过，问题看起来很简单，但是数组没有排序，因此常规方法（如二进制搜索）不起作用我对这个问题感到震惊了一天，希望有人能给我提示。我正在寻找一种更快地解决问题的方法，至少时间复杂度应该低于O（N ^ 3）。

My task is to find the number of lucky triples in a given list. The brute force way is to use three loops but it takes too much time to solve the problem. I wrote this one and the system respond "time exceed". The problems looks silly and easy but the array is unsorted so general methods like binary search do not work. I am stun in the problem for one day and hope someone can give me a hint. I am seeking a way to solve the problem faster, at least the time complexity should be lower than O(N^3).

推荐答案

简单的类似于动态编程的算法将在二次时间和线性空间中执行此操作，而您只需维护一个计数器 c [i] 表示列表中的每个项目f之前的整数将 L [i] 除。

A simple dynamic programming-like algorithm will do this in quadratic time and linear space. You just have to maintain a counter c[i] for each item in the list, that represents the number of previous integers that divides L[i].

然后，当您遍历列表并测试每个整数时 L [k] 和所有先前的项目 L [j] ，如果 L [j] 除以 L [k] ，您只需添加 c [j] （可能是0）到您的三元组的全球计数器，因为这还意味着确实存在 c [j] 个项目 L [i] 使得 L [i] 除以 L [j] 和 i < j 。

Then, as you go through the list and test each integer L[k] with all previous item L[j], if L[j] divides L[k], you just add c[j] (which could be 0) to your global counter of triples, because that also implies that there exist exactly c[j] items L[i] such that L[i] divides L[j] and 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）可以，那么就可以了。

There may be some better algorithm that uses fancy discrete maths to do it faster, but if O(n^2) is ok, this will do just fine.

关于您的评论：

• 为什么使用DP？我们可以清楚地将某些事物建模为具有从左到右的顺序（DP橙色标志），并且重新使用先前计算的值可能会很有趣，因为蛮力算法会多次执行完全相同的计算。

• Why DP? We have something that can clearly be modeled as having a left to right order (DP orange flag), and it feels like reusing previously computed values could be interesting, because the brute force algorithm does the exact same computations a lot of times.

如何从中得到解决方案？运行一个简单的示例（提示：最好从左到右处理输入）。在步骤 i 中，计算您可以从该特定点计算的内容（忽略i右边的所有内容），并尝试针对不同的 i's ：这就是您要缓存的内容。在这里，当您在步骤 k （ L [k]％L [j] == 0 ），您必须考虑 L [j] 会发生什么： 它的左边也有除数吗？这些都会给我们新的三倍让我们看看...但是等等！我们已经在步骤 j 中计算出了该值！让我们缓存该值！这就是您跳上座位的时候。

How to get from that to a solution? Run a simple example (hint: it should better be by treating input from left to right). At step i, compute what you can compute from this particular point (ignoring everything on the right of i), and try to pinpoint what you compute over and over again for different i's: this is what you want to cache. Here, when you see a potential triple at step k (L[k] % L[j] == 0), you have to consider what happens on L[j]: "does it have some divisors on its left too? Each of these would give us a new triple. Let's see... But wait! We already computed that on step j! Let's cache this value!" And this is when you jump on your seat.

这篇关于找到“幸运三元组”数量的更快方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！