1862-向下取整数对和
给你一个整数数组 nums
,请你返回所有下标对 0 <= i, j < nums.length
的 floor(nums[i] / nums[j])
结果之和。由于答案可能会很大,请你返回答案对109 + 7
取余 的结果。
函数 floor()
返回输入数字的整数部分。
示例 1:
**输入:** nums = [2,5,9]
**输出:** 10
**解释:**
floor(2 / 5) = floor(2 / 9) = floor(5 / 9) = 0
floor(2 / 2) = floor(5 / 5) = floor(9 / 9) = 1
floor(5 / 2) = 2
floor(9 / 2) = 4
floor(9 / 5) = 1
我们计算每一个数对商向下取整的结果并求和得到 10 。
示例 2:
**输入:** nums = [7,7,7,7,7,7,7]
**输出:** 49
提示:
1 <= nums.length <= 105
1 <= nums[i] <= 105
方法一:逆向思维
提示 1
一种常规的思路是枚举数组 nums 中的两个元素 x 和 y,计算 \lfloor \dfrac{x}{y} \rfloor 并求和。但这样做的时间复杂度为 O(n^2),会超出时间限制。
与其枚举 x 和 y,我们不妨枚举 y 和 \lfloor \dfrac{x}{y} \rfloor。
提示 2
令 d = \lfloor \dfrac{x}{y} \rfloor。如果我们枚举 y 和 d,那么满足要求的 x 应当在:
d \cdot y \leq x < (d+1) \cdot y
的范围内。
如果我们能统计出该范围内 x 的个数,那么将其乘以 d 再乘以 y 出现的次数,将它们进行求和即可得到最终的答案。
思路与算法
我们首先用 cnt}[x] 统计元素 x 在 nums 中出现的次数。记 upper 为数组 nums 中元素的最大值。
随后我们使用两重循环分别枚举 y 和 d。其中枚举 y 的循环的范围为 [1, \textit{upper}],枚举 d 的循环的范围为 [1, \lfloor \dfrac{\textit{upper} }{y} \rfloor]。根据提示 2,满足要求的 x 的数量为:
\sum_{x=d \cdot y}^{\min { (d+1) \cdot y-1, \textit{upper} } } \textit{cnt}[x]
虽然 x 的上界是 (d+1)\cdot y - 1,但是它显然也不能超过 upper。由于这一段求和的下标范围 x 是连续的,因此我们可以预处理出数组 cnt 的前缀和,记:
\textit{pre}[i] = \sum_{x=1}^i \textit{cnt}[i]
那么上式可以变为:
\textit{pre}\big[\min { (d+1) \cdot y-1, \textit{upper} }\big] - \textit{pre}[d \cdot y - 1]
就可以在 O(1) 的时间求出上式的值。
这样一来,将上式乘以 cnt}[y] \cdot d,再随着两重循环进行求和即可得到最终的答案。
代码
1 | class Solution { |
1 | class Solution: |
复杂度分析
时间复杂度:O(n + C\log C),其中 n 是数组 nums 的长度,C 是数组 nums 中的元素最大值,在本题中 C \leq 2\cdot 10^5。
计算数组 cnt 以及预处理前缀和数组 pre 需要的时间为 O(n + C);
在使用两重循环枚举 y 和 d 时,循环执行的次数为:
\sum_{y=1}^\textit{C} \sum_{d=1}^{\lfloor C/y \rfloor} 1 = O\left(\sum_{y=1}^\textit{C} C}{y} \right)
为调和级数,其趋近于 O(C \log C)。
因此总时间复杂度为 O(n + C\log C)。
空间复杂度:O(C),即为数组 cnt 和 pre 需要使用的空间。