class Solution {
public:
int sumOfFlooredPairs(vector<int>& nums) {
}
};
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 <= 1051 <= nums[i] <= 105原站题解
java 解法, 执行用时: 54 ms, 内存消耗: 54.7 MB, 提交时间: 2023-09-20 11:42:04
class Solution {
public int sumOfFlooredPairs(int[] a) {
long res=0,p=1000000007;
int n=a.length,maxx=0;
//找到最大的数，确定数组范围
for(int i=0;i<n;i++){
maxx=Math.max(maxx,a[i]);
}
int[] num=new int[maxx+1];
//计数
for(int i=0;i<n;i++)
num[ a[i] ]++;
//前缀和
for(int i=1;i<=maxx;i++)
num[i]+=num[i-1];
for(int i=1;i<=maxx;i++){
//x表示数字i的个数
long x=num[i]-num[i-1];
if(x==0)
continue;
//[i,i*2-1]、[i*2,i*3-1]、[i*3,i*4-1]，区间内的floor函数值都一样
for(int j=i;j<=maxx;j=j+i){
//y表示区间的个数,如果j+i-1>maxx则取maxx即可，防止数组溢出
long y=num[Math.min(j+i-1,maxx)]-num[j-1];
//倍数*区间数*个数
res=(res+(j/i)*y*x)%p;
}
}
return (int)res;
}
}
python3 解法, 执行用时: 2608 ms, 内存消耗: 28.1 MB, 提交时间: 2023-09-20 11:41:36
class Solution:
def sumOfFlooredPairs(self, nums: List[int]) -> int:
mod = 10**9 + 7
# 元素最大值
upper = max(nums)
cnt = [0] * (upper + 1)
for num in nums:
cnt[num] += 1
# 预处理前缀和
pre = [0] * (upper + 1)
for i in range(1, upper + 1):
pre[i] = pre[i - 1] + cnt[i]
ans = 0
for y in range(1, upper + 1):
# 一个小优化，如果数组中没有 y 可以跳过
if cnt[y]:
d = 1
while d * y <= upper:
ans += cnt[y] * d * (pre[min((d + 1) * y - 1, upper)] - pre[d * y - 1])
d += 1
return ans % mod
cpp 解法, 执行用时: 308 ms, 内存消耗: 271.7 MB, 提交时间: 2023-09-20 11:40:49
class Solution {
public:
int sumOfFlooredPairs(vector<int>& nums) {
vector<long long> arr(200010, 0);
vector<long long> sum(200010, 0);
int maxV = 0;
long long ret = 0;
for(auto it: nums){
maxV = max(maxV, it);
arr[it] ++;
}
for(int i = 1; i <= maxV * 2; ++i){
sum[i] = sum[i - 1] + arr[i];
}
for(int i = 1; i <= maxV; ++i){
if(arr[i] > 0){
for(long long j = 1; j * i <= maxV; ++j){
// 后面那部分意义是：数字i的出现次数 乘以 整数部分j 乘以 （数组中除以i的整数部分是j的数字的数量）
ret = (ret + (sum[(j + 1) * i - 1] - sum[j * i - 1]) * j * arr[i]) % 1000000007;
}
}
}
return ret;
}
};
golang 解法, 执行用时: 204 ms, 内存消耗: 12.4 MB, 提交时间: 2023-09-20 11:40:23
/**
* 统计每个数的出现次数 cnt，并计算次数的前缀和 sum。
* 然后枚举分母以及商，用前缀和计算对应的分子个数，
* 将分母个数 c、商 d、分子个数三者相乘即为每部分的结果，累加每部分的结果即为答案。
*/
func sumOfFlooredPairs(a []int) (ans int) {
cnt := make([]int, 2e5)
for _, v := range a {
cnt[v]++
}
sum := make([]int, 2e5+1)
for i, v := range cnt {
sum[i+1] = sum[i] + v
}
for i, c := range cnt {
if c > 0 {
for d := 1; d*i <= 1e5; d++ {
ans += c * d * (sum[(d+1)*i] - sum[d*i])
}
}
}
return ans % (1e9 + 7)
}