2022-09-07:给你一个由正整数组成的数组 nums 。 数字序列的 最大公约数 定义为序列中所有整数的共

2022-09-07:给你一个由正整数组成的数组 nums 。
数字序列的 最大公约数 定义为序列中所有整数的共有约数中的最大整数。
例如,序列 [4,6,16] 的最大公约数是 2 。
数组的一个 子序列 本质是一个序列,可以通过删除数组中的某些元素(或者不删除)得到。
例如,[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。
计算并返回 nums 的所有 非空 子序列中 不同 最大公约数的 数目 。
输入:nums = [5,15,40,5,6];
输出:7。

答案2022-09-07:

n/1 + n/2 + n/3 + n/4 + … + n/n 收敛于 O(N * logN),N是最大值,当做结论记住。

代码用rust编写。代码如下:

fn main() {
    let mut arr = vec![5, 15, 40, 5, 6];
    let ans = count_different_subsequence_gcds(&mut arr);
    println!("ans = {}", ans);
}

const MIN_VALUE: i32 = -1 << 31;

// n不是数字的个数,是数组中的最大值
// 体系学习班,
// 根据数据量猜解法,
// 要想通过测试,一定要让计算量不超过10的7次方~10的8次方
// n/1 + n/2 + n/3 + n/4 + ... + n/n -> O(N * logN)
fn count_different_subsequence_gcds(nums: &mut Vec<i32>) -> i32 {
    // 找到数组中的最大数!max
    let mut max = MIN_VALUE;
    for num in nums.iter() {
        max = get_max(max, *num);
    }
    // 1~max,哪个数有哪个数没有
    let mut set: Vec<bool> = vec![];
    for _ in 0..max + 1 {
        set.push(false);
    }
    for num in nums.iter() {
        set[*num as usize] = true;
    }
    let mut ans = 0;
    // a是当前想确定,是不是某个子序列的最大公约数,有a!
    let mut a = 1;
    while a <= max {
        // 1)找到,离a最近的,a的倍数!1 2 3 ... g就是
        let mut g = a;
        while g <= max {
            if set[g as usize] {
                break;
            }
            g += a;
        }
        // 2) 找到了a最近的倍数,g
        // g + 0 , g ?= a
        // g + a , g ?= a
        // g + 2a , g ?= a
        // g + 3a , g ?= a
        let mut b = g;
        while b <= max {
            if set[b as usize] {
                g = gcd(g, b);
                if g == a {
                    ans += 1;
                    break;
                }
            }
            b += a;
        }
        a+=1;
    }
    return ans;
}

fn gcd(m: i32, n: i32) -> i32 {
    if n == 0 {
        m
    } else {
        gcd(n, m % n)
    }
}

fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a > b {
        a
    } else {
        b
    }
}

执行结果如下:

在这里插入图片描述


左神java代码

本作品采用《CC 协议》,转载必须注明作者和本文链接
微信公众号:福大大架构师每日一题。最新面试题,涉及golang,rust,mysql,redis,云原生,算法,分布式,网络,操作系统。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!