首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >2025-05-23:数组的最大因子得分。用go语言,给定一个整数数组 nums。 定义“因子得分”为该数组中所有元素的最小公倍

2025-05-23:数组的最大因子得分。用go语言,给定一个整数数组 nums。 定义“因子得分”为该数组中所有元素的最小公倍

作者头像
福大大架构师每日一题
发布于 2025-05-23 02:26:50
发布于 2025-05-23 02:26:50
3800
代码可运行
举报
运行总次数:0
代码可运行

2025-05-23:数组的最大因子得分。用go语言,给定一个整数数组 nums。

定义“因子得分”为该数组中所有元素的最小公倍数(LCM)与最大公约数(GCD)相乘后的结果。

现在你最多可以移除数组中的一个元素,求在这种情况下,nums 的最大因子得分。

特别说明:

  • • 如果数组只剩一个数字,则其因子得分等于该数字自身。
  • • 如果数组为空,则因子得分为 0。

1 <= nums.length <= 100。

1 <= nums[i] <= 30。

输入: nums = [2,4,8,16]。

输出: 64。

解释:

移除数字 2 后,剩余元素的 GCD 为 4,LCM 为 16,因此最大因子得分为 4 * 16 = 64。

题目来自力扣3334。

解决思路

  1. 1. 理解因子得分:因子得分是数组的 LCM 和 GCD 的乘积。我们需要计算原始数组的因子得分,以及移除每一个可能的元素后的因子得分,然后取最大值。
  2. 2. 关键观察
    • GCD:移除一个元素后,剩余数组的 GCD 是原数组 GCD(移除的元素可能不是 GCD 的约束)或更大的值。
    • LCM:移除一个元素后,剩余数组的 LCM 是原数组 LCM(移除的元素可能是 LCM 的关键)或更小的值。
    • • 因此,我们需要高效计算移除每一个元素后的 GCD 和 LCM。
  3. 3. 预处理
    • 后缀 GCD 数组 (sufGcd)sufGcd[i] 表示从 nums[i]nums[n-1] 的 GCD。
    • 后缀 LCM 数组 (sufLcm)sufLcm[i] 表示从 nums[i]nums[n-1] 的 LCM。
    • • 这两个数组可以通过从后向前遍历 nums 来计算。
  4. 4. 计算原始因子得分
    • • 原始 GCD 是 sufGcd[0](即整个数组的 GCD)。
    • • 原始 LCM 是 sufLcm[0](即整个数组的 LCM)。
    • • 原始因子得分是 sufGcd[0] * sufLcm[0]
  5. 5. 枚举移除每一个元素
    • • 对于移除 nums[i],剩余数组是 nums[0..i-1]nums[i+1..n-1]
    • • 剩余数组的 GCD 是 gcd(prefixGcd, sufGcd[i+1]),其中 prefixGcdnums[0..i-1] 的 GCD。
    • • 剩余数组的 LCM 是 lcm(prefixLcm, sufLcm[i+1]),其中 prefixLcmnums[0..i-1] 的 LCM。
    • • 在遍历过程中维护 prefixGcdprefixLcm
      • • 初始时 prefixGcd = 0(因为 gcd(0, x) = x),prefixLcm = 1(因为 lcm(1, x) = x)。
      • • 遍历到 nums[i] 时,先计算移除 nums[i] 的因子得分,然后更新 prefixGcdprefixLcm
  6. 6. 取最大值
    • • 比较原始因子得分和所有移除一个元素后的因子得分,取最大值。

详细步骤

  1. 1. 初始化
    • • 计算数组长度 n
    • • 初始化 sufGcdsufLcm 数组,大小为 n+1
    • sufGcd[n] = 0(因为 gcd(0, x) = x),sufLcm[n] = 1(因为 lcm(1, x) = x)。
  2. 2. 填充后缀数组
    • • 从后向前遍历 nums
      • sufGcd[i] = gcd(sufGcd[i+1], nums[i])
      • sufLcm[i] = lcm(sufLcm[i+1], nums[i])
  3. 3. 计算原始因子得分
    • ans = sufGcd[0] * sufLcm[0]
  4. 4. 枚举移除每一个元素
    • • 初始化 prefixGcd = 0prefixLcm = 1
    • • 从左到右遍历 nums
      • • 对于 nums[i],计算移除后的 GCD 和 LCM:
        • currentGcd = gcd(prefixGcd, sufGcd[i+1])
        • currentLcm = lcm(prefixLcm, sufLcm[i+1])
        • currentScore = currentGcd * currentLcm
        • • 更新 ans = max(ans, currentScore)
      • • 更新 prefixGcdprefixLcm
        • prefixGcd = gcd(prefixGcd, nums[i])
        • prefixLcm = lcm(prefixLcm, nums[i])
  5. 5. 返回结果
    • • 返回 ans

时间和空间复杂度

  • 时间复杂度
    • • 填充 sufGcdsufLcm:O(n),因为每个元素处理一次,每次处理调用 gcdlcm(可以视为 O(1) 因为数字很小)。
    • • 枚举移除元素:O(n),同样每次处理调用 gcdlcm
    • • 总时间复杂度:O(n)。
  • 空间复杂度
    • sufGcdsufLcm 数组:O(n)。
    • • 其他变量:O(1)。
    • • 总空间复杂度:O(n)。

Go完整代码如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
package main

import (
    "fmt"
    "slices"
)

func maxScore(nums []int)int64 {
    n := len(nums)
    sufGcd := make([]int, n+1)
    sufLcm := make([]int, n+1)
    sufLcm[n] = 1
    for i, x := range slices.Backward(nums) {
        sufGcd[i] = gcd(sufGcd[i+1], x)
        sufLcm[i] = lcm(sufLcm[i+1], x)
    }

    ans := sufGcd[0] * sufLcm[0] // 不移除元素
    preGcd, preLcm := 0, 1
    for i, x := range nums { // 枚举移除 nums[i]
        ans = max(ans, gcd(preGcd, sufGcd[i+1])*lcm(preLcm, sufLcm[i+1]))
        preGcd = gcd(preGcd, x)
        preLcm = lcm(preLcm, x)
    }
    returnint64(ans)
}

func gcd(a, b int)int {
    for a != 0 {
        a, b = b%a, a
    }
    return b
}

func lcm(a, b int)int {
    return a / gcd(a, b) * b
}


func main() {
    nums := []int{2,4,8,16}
    result := maxScore(nums)
    fmt.Println(result)
}

Rust完整代码如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
fn gcd(mut a: i64, mut b: i64) ->i64 {
    while a != 0 {
        lettemp = a;
        a = b % a;
        b = temp;
    }
    b
}

fnlcm(a: i64, b: i64) ->i64 {
    a / gcd(a, b) * b
}

fnmax_score(nums: &[i64]) ->i64 {
    letn = nums.len();
    letmut suf_gcd = vec![0; n + 1];
    letmut suf_lcm = vec![1; n + 1];

    // 从后往前计算后缀的gcd和lcm
    foriin (0..n).rev() {
        suf_gcd[i] = gcd(suf_gcd[i + 1], nums[i]);
        suf_lcm[i] = lcm(suf_lcm[i + 1], nums[i]);
    }

    // 不移除元素的情况
    letmut ans = suf_gcd[0] * suf_lcm[0];
    letmut pre_gcd = 0;
    letmut pre_lcm = 1;

    foriin0..n {
        // 移除 nums[i]
        letcurr = gcd(pre_gcd, suf_gcd[i + 1]) * lcm(pre_lcm, suf_lcm[i + 1]);
        if curr > ans {
            ans = curr;
        }
        pre_gcd = gcd(pre_gcd, nums[i]);
        pre_lcm = lcm(pre_lcm, nums[i]);
    }

    ans
}

fnmain() {
    letnums = vec![2, 4, 8, 16];
    letresult = max_score(&nums);
    println!("{}", result);
}
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2025-05-22,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 福大大架构师每日一题 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 解决思路
  • 详细步骤
  • 时间和空间复杂度
  • Go完整代码如下:
  • Rust完整代码如下:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档