Hard

题目描述

给你一个整数数组 nums ，请你返回所有下标对 0 <= i, j < nums.length 的 floor(nums[i] / nums[j]) 结果之和。由于答案可能很大，请你返回答案对 10^9 + 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^5
  • 1 <= nums[i] <= 10^5

解题思路

这道题要求计算所有数对的向下取整除法和。直接暴力计算会超时，需要优化。

核心思路：利用频次统计和数学性质来减少重复计算。

  1. 频次统计：先统计每个数字的出现次数，相同的数字可以批量处理。

  2. 分组计算：对于除数 j，我们可以将被除数按照商值进行分组。具体来说，对于除数 j，商为 k 的被除数范围是 [k*j, (k+1)*j-1]。

  3. 前缀和优化：使用前缀和来快速计算某个范围内所有数字的频次总和。

算法步骤：

  • 统计每个数字的频次
  • 计算频次的前缀和
  • 对每个可能的除数，遍历所有可能的商值
  • 利用前缀和快速计算对应范围内被除数的总频次
  • 累加结果

时间复杂度从 O(n²) 优化到 O(n log n)，其中 n 是数组长度。

代码实现

class Solution {
public:
    int sumOfFlooredPairs(vector<int>& nums) {
        const int MOD = 1e9 + 7;
        int maxVal = *max_element(nums.begin(), nums.end());
        
        // 统计频次
        vector<int> freq(maxVal + 1, 0);
        for (int num : nums) {
            freq[num]++;
        }
        
        // 计算前缀和
        vector<long long> prefixSum(maxVal + 1, 0);
        for (int i = 1; i <= maxVal; i++) {
            prefixSum[i] = prefixSum[i - 1] + freq[i];
        }
        
        long long result = 0;
        
        // 对每个可能的除数
        for (int j = 1; j <= maxVal; j++) {
            if (freq[j] == 0) continue;
            
            // 对每个可能的商
            for (int k = 1; k * j <= maxVal; k++) {
                int left = k * j;
                int right = min((k + 1) * j - 1, maxVal);
                
                // 计算范围 [left, right] 内的频次总和
                long long count = prefixSum[right] - prefixSum[left - 1];
                
                // 累加到结果
                result = (result + (long long)k * count % MOD * freq[j] % MOD) % MOD;
            }
        }
        
        return result;
    }
};

class Solution:
    def sumOfFlooredPairs(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        max_val = max(nums)
        
        # 统计频次
        freq = [0] * (max_val + 1)
        for num in nums:
            freq[num] += 1
        
        # 计算前缀和
        prefix_sum = [0] * (max_val + 1)
        for i in range(1, max_val + 1):
            prefix_sum[i] = prefix_sum[i - 1] + freq[i]
        
        result = 0
        
        # 对每个可能的除数
        for j in range(1, max_val + 1):
            if freq[j] == 0:
                continue
            
            # 对每个可能的商
            k = 1
            while k * j <= max_val:
                left = k * j
                right = min((k + 1) * j - 1, max_val)
                
                # 计算范围 [left, right] 内的频次总和
                count = prefix_sum[right] - prefix_sum[left - 1]
                
                # 累加到结果
                result = (result + k * count * freq[j]) % MOD
                k += 1
        
        return result

public class Solution {
    public int SumOfFlooredPairs(int[] nums) {
        const int MOD = 1000000007;
        int maxVal = nums.Max();
        
        // 统计频次
        int[] freq = new int[maxVal + 1];
        foreach (int num in nums) {
            freq[num]++;
        }
        
        // 计算前缀和
        long[] prefixSum = new long[maxVal + 1];
        for (int i = 1; i <= maxVal; i++) {
            prefixSum[i] = prefixSum[i - 1] + freq[i];
        }
        
        long result = 0;
        
        // 对每个可能的除数
        for (int j = 1; j <= maxVal; j++) {
            if (freq[j] == 0) continue;
            
            // 对每个可能的商
            for (int k = 1; k * j <= maxVal; k++) {
                int left = k * j;
                int right = Math.Min((k + 1) * j - 1, maxVal);
                
                // 计算范围 [left, right] 内的频次总和
                long count = prefixSum[right] - prefixSum[left - 1];
                
                // 累加到结果
                result = (result + (long)k * count % MOD * freq[j] % MOD) % MOD;
            }
        }
        
        return (int)result;
    }
}

var sumOfFlooredPairs = function(nums) {
    const MOD = 1e9 + 7;
    const maxVal = Math.max(...nums);
    
    // 统计频次
    const freq = new Array(maxVal + 1).fill(0);
    for (const num of nums) {
        freq[num]++;
    }
    
    // 计算前缀和
    const prefixSum = new Array(maxVal + 1).fill(0);
    for (let i = 1; i <= maxVal; i++) {
        prefixSum[i] = prefixSum[i - 1] + freq[i];
    }
    
    let result = 0;
    
    // 对每个可能的除数
    for (let j = 1; j <= maxVal; j++) {
        if (freq[j]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n + m log m)，其中 n 是数组长度，m 是数组中的最大值。统计频次需要 O(n)，对每个除数遍历所有商需要 O(m log m)
空间复杂度O(m)，需要存储频次数组和前缀和数组，其中 m 是数组中的最大值