原文链接: https://leetcode-cn.com/problems/sum-of-floored-pairs

英文原文

Given an integer array nums, return the sum of floor(nums[i] / nums[j]) for all pairs of indices 0 <= i, j < nums.length in the array. Since the answer may be too large, return it modulo 109 + 7.

The floor() function returns the integer part of the division.

 

Example 1:

Input: nums = [2,5,9]
Output: 10
Explanation:
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
We calculate the floor of the division for every pair of indices in the array then sum them up.

Example 2:

Input: nums = [7,7,7,7,7,7,7]
Output: 49

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

中文题目

给你一个整数数组 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.确定方向
首先我们可以知道，对于floor函数，例如floor(x/y)中，假设y一定，则有多个x使得floor(x/y)相同；
例如y=9，则
x=[9,17]时floor函数都为1；
x=[18,26]时floor函数都为2；
x=[27,35]时floor函数都是3；
显然需要进行区间计数，容易联想到前缀和

2.看数据范围
数组长度和元素大小范围都在100000内，可以直接开大数组num
计数数组：num[i]表示元素i的个数
升级成前缀和数组：num[i]表示[0,i]的元素个数总和，num[i]-num[i-1]则表示元素i的个数
这里最大元素作为数组长度，不需要每次都开到100001，节省空间

3.倍数
对于元素i，每次找区间
[i,i×2-1] [i×2,i×3-1] [i×3,i×4-1] ….[i×(j-1),i×j-1]之间的元素个数，倍数关系在循环中用j表示，即前面的×1×2×3；
倍数×区间内的元素总个数 = 元素i在该段区间的函数值总和；
元素i的个数×倍数×区间内的元素总个数 = 所有i在该段区间的函数值总和；
再对多段区间进行累加即可；

4.注意越界情况
极限数据100000×100000会int溢出，运算期间用long，最后转int
当i×j-1>maxx时直接使用i×j作为数组下标会使得数组越界；

5.详看代码

/** 5212. 向下取整数对和
 * 求所有floor(nums[i] / nums[j])之和
 * 前缀和计数
 */
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;
}

如果本篇题解帮到你了，可以给个赞支持一下吗？

统计信息

通过次数	提交次数	AC比率
2338	7467	31.3%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言