数组乘积中的不同质因数数目
难度:
标签:
题目描述
Given an array of positive integers nums, return the number of distinct prime factors in the product of the elements of nums.
Note that:
- A number greater than
1is called prime if it is divisible by only1and itself. - An integer
val1is a factor of another integerval2ifval2 / val1is an integer.
Example 1:
Input: nums = [2,4,3,7,10,6] Output: 4 Explanation: The product of all the elements in nums is: 2 * 4 * 3 * 7 * 10 * 6 = 10080 = 25 * 32 * 5 * 7. There are 4 distinct prime factors so we return 4.
Example 2:
Input: nums = [2,4,8,16] Output: 1 Explanation: The product of all the elements in nums is: 2 * 4 * 8 * 16 = 1024 = 210. There is 1 distinct prime factor so we return 1.
Constraints:
1 <= nums.length <= 1042 <= nums[i] <= 1000
代码结果
运行时间: 36 ms, 内存: 17.0 MB
/*
* 思路：
* 1. 使用Java Stream API来处理数组。
* 2. 对每个数字求其质因数并将其放入一个集合中以去重。
* 3. 最后统计集合中的质因数数量。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public int distinctPrimeFactors(int[] nums) {
return Arrays.stream(nums)
.boxed()
.flatMap(num -> getPrimeFactors(num).stream())
.collect(Collectors.toSet())
.size();
}
private Set<Integer> getPrimeFactors(int num) {
Set<Integer> factors = new HashSet<>();
for (int i = 2; i <= num / i; i++) {
while (num % i == 0) {
factors.add(i);
num /= i;
}
}
if (num > 1) {
factors.add(num);
}
return factors;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums1 = {2, 4, 3, 7, 10, 6};
System.out.println(solution.distinctPrimeFactors(nums1)); // 输出: 4
int[] nums2 = {2, 4, 8, 16};
System.out.println(solution.distinctPrimeFactors(nums2)); // 输出: 1
}
}
解释
方法:
该题解通过遍历数组中每个元素，使用试除法找出每个元素的所有质因数，并将这些质因数存储在集合中，以去除重复的质因数。最终，返回集合中元素的数量，即不同质因数的数目。试除法从2开始，直到sqrt(x)，检查是否能整除x。如果可以，将该因数加入集合，并将x除以该因数直至不再能整除。如果在结束内层循环后x大于1，则x本身是一个质数，也将其加入集合。
时间复杂度:
O(n * sqrt(m))
空间复杂度:
O(u)
代码细节讲解
🦆
在处理大数字的情况下，这种算法的时间复杂度是多少，是否会因为数字过大导致性能问题？
▷🦆
你是如何确定只需要检查到每个数字的平方根来找出所有质因数的？
▷🦆
如果数组中的数字非常大，例如接近整数的上限，这种算法是否还能有效运行，有无可能的溢出或性能下降？
▷