Java 中查找数组的最大因子分数

最大因子得分是指找出数组中所有元素的因数（约数）中出现频率最高的那个因数。我们观察数组中每个整数的约数，并统计它们的出现次数。出现次数最多的那个因数就是最大因子得分。如果多个因数具有相同的最高出现次数，则选择最大的那个因数。这种方法在数论和优化问题中，有助于分析数组中数字的共同约数。

现在给定一个整数 数组 nums。数组的因子得分为数组中每个元素的 最小公倍数 (LCM) 和 最大公约数 (GCD) 的乘积。在从 nums 中最多移除一个元素后，返回最大的因子得分。

示例 1

输入

int num = [7, 14, 21, 28]

输出

数组的最大因子得分为 588

解释

移除 7 后剩余的元素是 [14, 21, 28]。

GCD(14, 21, 28) = 7

LCM(14, 21, 28) = 84

因子得分 = 7 × 84 = 588

移除 14 后剩余的元素是 [7, 21, 28]。

GCD(7, 21, 28) = 7

LCM(7, 21, 28) = 84

因子得分 = 7 × 84 = 588

移除 21 后剩余的元素是 [7, 14, 28]。

GCD(7, 14, 28) = 7

LCM(7, 14, 28) = 28

因子得分 = 7 × 28 = 196

移除 28 后剩余的元素是 [7, 14, 21]。

GCD(7, 14, 21) = 7

LCM(7, 14, 21) = 42

因子得分 = 7 × 42 = 294

示例 2

输入

int num = [5, 10, 20, 25]

输出

数组的最大因子得分为 500

解释

移除 5 后剩余的元素是 [10, 20, 25]。

GCD(10, 20, 25) = 5

LCM(10, 20, 25) = 100

因子得分 = 5 × 100 = 500

移除 10 后剩余的元素是 [5, 20, 25]。

GCD(5, 20, 25) = 5

LCM(5, 20, 25) = 100

因子得分 = 5 × 100 = 500

移除 20 后剩余的元素是 [5, 10, 25]。

GCD(5, 10, 25) = 5

LCM(5, 10, 25) = 50

因子得分 = 5 × 50 = 250

移除 25 后剩余的元素是 [5, 10, 20]。

GCD(5, 10, 20) = 5

LCM(5, 10, 20) = 20

因子得分 = 5 × 20 = 100

示例 3

输入

int num = [4]

输出

数组的最大因子得分为 16

解释

移除 4 后剩余的元素是 []（空数组）。

空数组的 GCD 是未定义的，但由于只剩一个元素，我们假设它是 4。

空数组的 LCM 也是未定义的，但由于只剩一个元素，我们假设它是 4。

因子得分 = 4 × 4 = 16

方法：暴力算法

为了确定最大因子得分，上面的代码中的算法首先定义了一个名为 Calculategcd 的函数，该函数使用欧几里得算法来查找两个数字的最大公约数 (GCD)。为了获得因子得分，get 方法会遍历数字列表，删除指定索引 x 处的元素，然后计算剩余项的 GCD 和 LCM。对于每个元素，使用公式 (lcm * a) / Calculategcd(lcm, a) 更新 LCM。通过为每个索引调用 get 方法，maxScore 方法然后确定每个潜在元素排除的因子得分，并返回找到的最大因子得分。这种暴力方法比较了每个可能的项目子集的得分，以确保选择最大的因子得分。

实施

输出

 
The  Maximum Factor Score is: 588   

复杂度分析

上述代码的时间复杂度为 O(n² log A)，空间复杂度为 O(n)，其中 'n' 代表元素的数量，'A' 代表数组中的最大值。