1862. 向下取整数对和Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你一个整数数组 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 <= 10⁵
1 <= nums[i] <= 10⁵

# 思路

for

# 解法

class Solution {
    // 
    public int sumOfFlooredPairs(int[] nums) {
        int n = nums.length, mod = 1000000007, max = 0;
        long sum = 0;
        for (int x : nums) {
            max = Math.max(max, x);
            sum += x;
        }
        int[] f = new int[max + 1];
        for (int x : nums) f[x]++;
        
        for (int i = 1; i <= max; i++) f[i] += f[i - 1];
        
        long res = 0;
        
        for (int i = 0; i < n; i++) {
            // 避免 1 导致复杂度退化
            if (nums[i] == 1) res = res + sum;
            else {
                for (int j = nums[i], cost = 1; j <= max; j += nums[i], cost++) {
                    res = (res + (f[Math.min(max, j + nums[i] - 1)] - f[j - 1]) * cost) % mod;
                }
            }
            
        }
        return (int)(res % mod);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# 总结

分析出几种情况，然后分别对各个情况实现

#Java