向下取整数对和
难度:
标签:
题目描述
代码结果
运行时间: 568 ms, 内存: 35.7 MB
/*
* 思路:
* 1. 使用 Java Stream 对每一对 (i, j) 进行计算。
* 2. 使用 flatMap 和 mapToLong 来计算每个商的 floor 值。
* 3. 累加结果并取模。
*/
import java.util.stream.IntStream;
public class Solution {
public int sumOfFlooredPairs(int[] nums) {
int MOD = 1000000007;
long sum = IntStream.range(0, nums.length)
.flatMap(i -> IntStream.range(0, nums.length)
.map(j -> nums[i] / nums[j]))
.mapToLong(x -> x)
.reduce(0, (a, b) -> (a + b) % MOD);
return (int) sum;
}
}
解释
方法:
这个题解采用了哈希表和前缀和的方法来高效地计算所有数对的向下取整和。首先,使用Counter来计数数组中每个数字出现的次数。接着,创建一个数组store,其长度为数组中最大数加一。对于每一个在nums中出现的数x,更新store数组,将x的倍数的位置增加x出现的次数。这样做是因为,任意数y被x整除的商就是y/x。之后,计算store的前缀和,这样每个store[y]就包含了所有小于等于y的数除以其它数的商的和。最后,通过遍历nums数组,累加这些前缀和得到最终结果,并取模10^9+7返回。
时间复杂度:
O(n + m log m)
空间复杂度:
O(m)
代码细节讲解
🦆
为什么选择使用哈希表来计数数组中的元素而不是直接遍历数组进行计算?
▷🦆
可以解释一下为什么在处理store数组时,需要将每个数字x的倍数位置都增加x出现的次数吗?
▷🦆
计算store的前缀和如何帮助我们快速获取所有小于等于y的数除以其他数的商的和?
▷🦆
在最终的结果计算中,为什么需要对结果取模10^9+7?
▷