leetcode
leetcode 1151 ~ 1200
向下取整数对和

向下取整数对和

难度:

标签:

题目描述

代码结果

运行时间: 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)

代码细节讲解

🦆
为什么选择使用哈希表来计数数组中的元素而不是直接遍历数组进行计算?
使用哈希表(Counter)来计数是因为这种方法可以快速统计每个数字的出现次数,并且可以直接访问每个唯一值及其频率。如果直接在遍历时计算,则每次更新操作可能需要遍历整个数组来查找相同的值,这将使时间复杂度增加。哈希表优化了这一过程,使得时间复杂度降低,并且代码实现更简洁高效。
🦆
可以解释一下为什么在处理store数组时,需要将每个数字x的倍数位置都增加x出现的次数吗?
在store数组中,每个索引位置y代表的是所有小于等于y的数字除以其他数字的商的和。对于一个特定的数字x,它能整除的数字包括x, 2x, 3x等。因此,对于nums中每一个出现的x,我们需要在store数组中x的所有倍数的位置上累加x出现的次数。这样做是为了在计算前缀和时,能够通过store[y]快速得到所有合法的商的累加值,这些商是由所有小于等于y的数字除以x得到的。
🦆
计算store的前缀和如何帮助我们快速获取所有小于等于y的数除以其他数的商的和?
计算store数组的前缀和后,每个位置y的值将包含所有小于等于y的索引处的值的总和。这意味着store[y]实际上包含了所有小于等于y的数除以所有可能的数x(x是数组nums中的元素)的商的和。通过前缀和,我们可以在O(1)的时间内直接获取到任何y值对应的累计商的和,这极大地优化了查询效率。
🦆
在最终的结果计算中,为什么需要对结果取模10^9+7?
对结果取模10^9+7是一个常见的技巧,主要用于防止在处理非常大的整数时发生溢出,并且可以保持最终结果的大小在一个合理的范围内。10^9+7是一个大的质数,常用于编程竞赛和算法实现中,因为它可以减少在模运算中的冲突,并且配合使用快速幂等算法,可以高效地处理大数的问题。

相关问题