2521. 数组乘积中的不同质因数数目

题目描述

给你一个正整数数组 nums ，对 nums 所有元素求积之后，找出并返回乘积中 不同质因数 的数目。

注意：

质数是指大于 1 且仅能被 1 及自身整除的数字。
如果 val2 / val1 是一个整数，则整数 val1 是另一个整数 val2 的一个因数。

示例 1：

输入：nums = [2,4,3,7,10,6]
输出：4
解释：
nums 中所有元素的乘积是：2 * 4 * 3 * 7 * 10 * 6 = 10080 = 2⁵ * 3² * 5 * 7 。
共有 4 个不同的质因数，所以返回 4 。

示例 2：

输入：nums = [2,4,8,16]
输出：1
解释：
nums 中所有元素的乘积是：2 * 4 * 8 * 16 = 1024 = 2¹⁰ 。
共有 1 个不同的质因数，所以返回 1 。

提示：

1 <= nums.length <= 10⁴
2 <= nums[i] <= 1000

解法

方法一：哈希表 + 质因数分解

对于数组中的每个元素，先对其进行质因数分解，然后将分解出的质因数加入哈希表中。最后返回哈希表的大小即可。

时间复杂度 $O(n \times \sqrt{m})$，空间复杂度 $O(\frac{m}{\log m})$，其中 $n$ 和 $m$ 分别为数组的长度和数组中元素的最大值。

Python3JavaC++GoTypeScript

class Solution:
    def distinctPrimeFactors(self, nums: List[int]) -> int:
        s = set()
        for n in nums:
            i = 2
            while i <= n // i:
                if n % i == 0:
                    s.add(i)
                    while n % i == 0:
                        n //= i
                i += 1
            if n > 1:
                s.add(n)
        return len(s)

class Solution {
    public int distinctPrimeFactors(int[] nums) {
        Set<Integer> s = new HashSet<>();
        for (int n : nums) {
            for (int i = 2; i <= n / i; ++i) {
                if (n % i == 0) {
                    s.add(i);
                    while (n % i == 0) {
                        n /= i;
                    }
                }
            }
            if (n > 1) {
                s.add(n);
            }
        }
        return s.size();
    }
}

class Solution {
public:
    int distinctPrimeFactors(vector<int>& nums) {
        unordered_set<int> s;
        for (int& n : nums) {
            for (int i = 2; i <= n / i; ++i) {
                if (n % i == 0) {
                    s.insert(i);
                    while (n % i == 0) {
                        n /= i;
                    }
                }
            }
            if (n > 1) {
                s.insert(n);
            }
        }
        return s.size();
    }
};

func distinctPrimeFactors(nums []int) int {
    s := map[int]bool{}
    for _, n := range nums {
        for i := 2; i <= n/i; i++ {
            if n%i == 0 {
                s[i] = true
                for n%i == 0 {
                    n /= i
                }
            }
        }
        if n > 1 {
            s[n] = true
        }
    }
    return len(s)
}

function distinctPrimeFactors(nums: number[]): number {
    const s: Set<number> = new Set();
    for (let n of nums) {
        let i = 2;
        while (i <= n / i) {
            if (n % i === 0) {
                s.add(i);
                while (n % i === 0) {
                    n = Math.floor(n / i);
                }
            }
            ++i;
        }
        if (n > 1) {
            s.add(n);
        }
    }
    return s.size;
}

2521. 数组乘积中的不同质因数数目

题目描述

解法

方法一：哈希表 + 质因数分解

评论