统计可以被 K 整除的下标对数目
难度:
标签:
题目描述
代码结果
运行时间: 95 ms, 内存: 27.1 MB
/*
* 题目思路:
* 1. 使用 Java Stream 遍历数组的所有可能的下标对 (i, j),其中 i < j。
* 2. 对于每一对 (i, j),计算 nums[i] * nums[j]。
* 3. 使用 filter 函数过滤出乘积能被 k 整除的对。
* 4. 计算这些对的数量。
*/
import java.util.stream.IntStream;
public class Solution {
public int countPairs(int[] nums, int k) {
return (int) IntStream.range(0, nums.length)
.boxed()
.flatMap(i -> IntStream.range(i + 1, nums.length)
.filter(j -> (nums[i] * nums[j]) % k == 0)
.mapToObj(j -> new int[]{i, j}))
.count();
}
}
解释
方法:
本题解采用了数学和哈希表的方法来优化解决问题。首先用哈希表freq统计数组中每个元素与k的最大公因数(gcd)出现的频次。然后对这个哈希表中的元素(gcd值及其出现次数)进行排序。对于每一对gcd值,如果它们的乘积能被k整除,则表示存在多个满足条件的下标对(i, j),即这两个gcd值对应的原数组元素组合的所有可能。对于相同的gcd值,需要使用组合数公式来计算可能的下标对数。通过这种方法,将问题转化为了较少数量的gcd值的组合问题,从而避免了直接的n^2复杂度的暴力解法。
时间复杂度:
O(u^2 + u log u + n log k)
空间复杂度:
O(u)
代码细节讲解
🦆
为什么在处理计数时要使用最大公因数(gcd)而不是直接考虑nums[i]和nums[j]的乘积?
▷🦆
题解中提到了使用bisect_left进行查找,这种查找方法的目的是什么?如何确保它能找到正确的位置?
▷🦆
在处理相同gcd值的组合情况时,为什么可以使用组合数公式c[i][1] * (c[i][1] - 1) // 2来计算下标对数?
▷🦆
在题解中,排序操作是如何影响整体算法性能的?为什么选择排序这些gcd值?
▷