F_JustWei's Studio.

5212. 向下取整数对和

leetcode
字数统计: 372阅读时长: 1 min
2021/05/16 Share

5212. 向下取整数对和

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

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

示例 1：

1
2
3
4
5
6
7
8
9
输入：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：

1
2
输入：nums = [7,7,7,7,7,7,7]
输出：49

提示：

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

思路：

前缀和。

c++代码：

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
class Solution {
private:
    const int MOD = 1e9 + 7;
    using LL = long long;
public:
    int sumOfFlooredPairs(vector<int>& nums) {
        int MAX = *max_element(nums.begin(), nums.end()) + 1;
        //前缀和
        vector<int> cnts(MAX);
        for (int& x : nums) {
            cnts[x]++;
        }
        for (int i = 1; i < MAX; i++) {
            cnts[i] += cnts[i - 1];
        }

        LL ans = 0LL;
        for (int i = 1; i < MAX; i++) {
            if (cnts[i]) {
                for (int j = 1; j * i < MAX; j++) {
                    int l = j * i;//左边界，i 的 j 倍 = 左边界
                    int r = min(MAX - 1, (j + 1) * i - 1);//右边界，检查会不会超出范围
                    LL sum = (cnts[r] - cnts[l - 1]) * j % MOD;//这个范围内的总和
                    ans = (ans + sum * (cnts[i] - cnts[i - 1])) % MOD;//ans + 访问总和 * i 的个数 
                }
            }
        }
        return ans;
    }
};

原文作者：F_JustWei

原文链接：http://139.196.79.90/2021/05/16/5212-%E5%90%91%E4%B8%8B%E5%8F%96%E6%95%B4%E6%95%B0%E5%AF%B9%E5%92%8C/

发表日期：May 16th 2021, 2:41:56 pm

更新日期：May 16th 2021, 2:45:59 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 5212. 向下取整数对和
    1. 1.0.1. 示例 1：
    2. 1.0.2. 示例 2：
    3. 1.0.3. 提示：
    4. 1.0.4. 思路：
    5. 1.0.5. c++代码：
Total : 130
2021
2019
leetcode 动态规划 字符串 树 数据结构 C++ STL algorithm 容器 操作系统 软考 Java PTA 计算机网络 UML 迭代器 C JSON 信息安全 模板 多媒体， 软考 数据库 软件工程 排序 Spring 人机交互