千问 LeetCode 1862题的Python代码怎么写？

这是 LeetCode 1862 题“向下取整数对和”的 Python 代码实现。这道题如果直接双重循环暴力求解会超时因此我们采用“前缀和 倍数枚举”的策略将时间复杂度优化到 O(M log M)其中 M 是数组中的最大值。 Python 代码实现class Solution:def sumOfFlooredPairs(self, nums: List[int]) - int:MOD 10**9 7# 1. 找到数组中的最大值确定计数数组的大小max_val max(nums)# 2. 统计每个数字出现的频率# count[i] 表示数字 i 在 nums 中出现的次数count [0] * (max_val 1)for num in nums:count[num] 1# 3. 计算前缀和# prefix_sum[i] 表示数值在 [0, i] 范围内的元素总个数# 这样可以在 O(1) 时间内查询任意区间 [L, R] 内的元素个数prefix_sum [0] * (max_val 1)prefix_sum[0] count[0]for i in range(1, max_val 1):prefix_sum[i] prefix_sum[i - 1] count[i]ans 0# 4. 遍历每一个可能的数字作为分母for denominator in range(1, max_val 1):# 如果该数字不存在于数组中跳过if count[denominator] 0:continue# 5. 枚举商倍数# 我们固定分母为 denominator枚举商 k# 此时分子 numerator 的范围是 [k * denominator, (k 1) * denominator - 1]# 只要 k * denominator 0 else 0)if count_in_range 0:# 贡献值 (该范围内元素个数) * (商 k) * (分母出现的次数)# 分母出现次数是因为数组中可能有多个相同的分母contribution count_in_range * k * count[denominator]ans (ans contribution) % MODk 1return ans 算法核心逻辑解析1. 为什么使用前缀和题目要求计算 sum lfloor frac{nums[i]}{nums[j]} rfloor。如果我们固定分母 nums[j] x那么对于不同的分子 nums[i]lfloor frac{nums[i]}{x} rfloor 的结果是分段的。例如 x2* 分子在 [0, 1]结果为 0* 分子在 [2, 3]结果为 1* 分子在 [4, 5]结果为 2* ...* 分子在 [2k, 2k1]结果为 k前缀和数组 prefix_sum 让我们能瞬间算出数组中有多少个元素落在 [2k, 2k1] 这个区间内而不需要遍历整个数组。2. 复杂度分析* 时间复杂度O(M log M)其中 M 是数组中的最大值。* 外层循环遍历分母最多 M 次。* 内层循环枚举倍数商对于分母 x循环次数约为 M/x。* 总次数约为 M/1 M/2 M/3 ... M/M M times (1 1/2 ... 1/M) approx M ln M。* 空间复杂度O(M)用于存储频率数组和前缀和数组。3. 举例说明假设 nums [2, 5, 9]* 频率count[2]1, count[5]1, count[9]1。* 当分母为 2 时 (count[2]1)* 商为 1分子范围 [2, 3]。数组中有 1 个 (即2)。贡献 1 times 1 times 1 1。* 商为 2分子范围 [4, 5]。数组中有 1 个 (即5)。贡献 1 times 2 times 1 2。* 商为 4分子范围 [8, 9]。数组中有 1 个 (即9)。贡献 1 times 4 times 1 4。* 分母为 2 的总贡献1247。* 当分母为 5 时* 商为 1分子范围 [5, 9]。有 2 个 (5, 9)。贡献 2 times 1 times 1 2。* 当分母为 9 时* 商为 1分子范围 [9, 17]。有 1 个 (9)。贡献 1 times 1 times 1 1。* 总和7 2 1 10。这个逻辑与题目示例完全吻合。