Leetcode 1862 向下取整数对和 ( Sum of Floored Pairs *Hard* ) 题解分析

题目介绍

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 10^9 + 7.

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

对应中文
给你一个整数数组 nums ，请你返回所有下标对 0 <= i, j < nums.length 的 floor(nums[i] / nums[j]) 结果之和。由于答案可能会很大，请你返回答案对10^9 + 7 取余 的结果。

函数 floor() 返回输入数字的整数部分。

示例

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 <= 10^5
• 1 <= nums[i] <= 10^5

简析

这题不愧是 hard，要不是看了讨论区的一个大神的解答感觉从头做得想好久，
主要是两点，对于任何一个在里面的数，随便举个例子是 k，最简单的就是循环所有数对 k 除一下，
这样效率会很低，那么对于 k 有什么规律呢，就是对于所有小于 k 的数，往下取整都是 0，所以不用考虑，
对于所有大于 k 的数我们可以分成一个个的区间，[k,2k-1),[2k,3k-1),[3k,4k-1)……对于这些区间的
除了 k 往下取整，每个区间内的都是一样的，所以可以简化为对于任意一个 k，我只要知道与k 相同的有多少个，然后比 k 大的各个区间各有多少个数就可以了

代码

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

static final int MAXE5 = 100_000;

static final int MODULUSE9 = 1_000_000_000 + 7;

public int sumOfFlooredPairs(int[] nums) {
    int[] counts = new int[MAXE5+1];
    for (int num : nums) {
        counts[num]++;
    }
    // 这里就是很巧妙的给后一个加上前一个的值，这样其实前后任意两者之差就是这中间的元素数量
    for (int i = 1; i <= MAXE5; i++) {
        counts[i] += counts[i - 1];
    }
    long total = 0;
    for (int i = 1; i <= MAXE5; i++) {
        long sum = 0;
        if (counts[i] == counts[i-1]) {
            continue;
        }
        for (int j = 1; i*j <= MAXE5; j++) {
            int min = i * j - 1;
            int upper = i * (j + 1) - 1;
            // 在每一个区间内的数量，
            sum += (counts[Math.min(upper, MAXE5)] - counts[min]) * (long)j;
        }
        // 左边乘数的数量，即 i 位置的元素数量
        total = (total + (sum % MODULUSE9  ) * (counts[i] - counts[i-1])) % MODULUSE9;
    }
    return (int)total;
}

贴出来大神的解析,解析

结果