时间戳

首页 > 解决方案 > 在给定数组中查找 LCM 值最小的对

arrays - 在给定数组中查找 LCM 值最小的对

问题描述

我最近遇到了一个关于竞争性编程竞赛的问题。给定一个整数数组，找到 LCM 最小值的一对数组元素的索引。

我知道有一个简单的双循环 O(n^2) 解决方案，但正如预期的那样，它给出了时间限制异常。我听说动态编程用于优化蛮力方法，但我不知道如何将这个问题划分为子问题，以便有一个最佳的子结构。

我可以得到任何方向来使用 DP 解决这个问题吗？或者有什么更好的方法？谢谢。

标签： arraysalgorithmdata-structuresdynamic-programming

解决方案

（假设为正数。）

最小的 LCM 可能源于最小的元素，因此要修剪尝试值，可以对数组进行排序。

int[] v = { ... };

int minLCM = Integer.MAX_VALUE;
int bestVi = -1;
int bestVj = -1;
Arrays.sort(v);
for (int i = 0; i < v.length; ++i) {
    int vi = v[i];
    //                                  _____________
    for (int j = i + 1; j < v.length && v[j] < minLCM; ++j) {
        int vj = v[j];
        int lcm = lcm(vi, vj);
        if (lcm < minLcm) {
            minLCM = lcm;
            bestVi = vi;
            bestVj = vj;
        }
    }
}

修剪：

lcm(vi, vj) >= vi
lcm(vi, vj) >= vj
(lcm(vi, vj) <= vi*vj

这种修剪只能在 for-j 循环中完成，因为vj >= vi.

如果你有一个（最多²log value）主要因素的列表，则可以进行更好的修剪。由于因子分解成本也很高，例如，人们可能只尝试 (2, 3, 5, 7)。

更好的循环也可以通过替换两个嵌套循环来实现，以便最小的 (vi, vj) ​​先出现。高于 (v0, v100) 位于 (v1, v2) 之前。循环增加 i+j。

i j
0 1
0 2
0 3
1 2
0 4
1 3
0 5
1 4
2 3
...

（使用对角线的循环计数器的数学是一个很好的谜题。真的应该完成。）

虽然O(n²)这可能仍然有效。

有时编程语言也很重要，在这些情况下，人们通常会看到 C 的贡献。在这种情况下，使用 Ruby 可能会适得其反。

推荐阅读