题目
给你一个整数数组 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
分析
时间复杂度
O(nsqrt(n))。两层循环，第一层枚举商，第二层枚举除数。当商为1时，第二层循环n次。当商为2时，第二层循环n/2次。当商为3时，第三层循环n/3… 。故总的时间复杂度为：n +n/2 + n/3… 为：O(nsqrt(n))。
原理
已知商i除数j，被出数的范围是：[i*j,(i+1)*j) 左闭右开
代码
复用代码
template class C1097Int { public: C1097Int(long long llData = 0) :m_iData(llData% MOD) { } C1097Int operator+(const C1097Int& o)const { return C1097Int(((long long)m_iData + o.m_iData) % MOD); } C1097Int& operator+=(const C1097Int& o) { m_iData = ((long long)m_iData + o.m_iData) % MOD; return this; } C1097Int& operator-=(const C1097Int& o) { m_iData = (m_iData + MOD - o.m_iData) % MOD; return this; } C1097Int operator-(const C1097Int& o) { return C1097Int((m_iData + MOD - o.m_iData) % MOD); } C1097Int operator(const C1097Int& o)const { return((long long)m_iData * o.m_iData) % MOD; } C1097Int& operator=(const C1097Int& o) { m_iData = ((long long)m_iData * o.m_iData) % MOD; return *this; } bool operator<(const C1097Int& o)const { return m_iData < o.m_iData; } C1097Int pow(long long n)const { C1097Int iRet = 1, iCur = *this; while (n) { if (n & 1) { iRet *= iCur; } iCur *= iCur; n >>= 1; } return iRet; } C1097Int PowNegative1()const { return pow(MOD - 2); } int ToInt()const { return m_iData; } private: int m_iData = 0;; };
核心代码
class Solution { public: int sumOfFlooredPairs(vector& nums) { const int iMax = std::max_element(nums.begin(), nums.end()); vector vCount(iMax + 1); for (const auto& n : nums) { vCount[n]++; } vector vPreSum = { 0 };//vPreSum[i]记录值为[0,i)的数量 for (int i = 0; i <= iMax; i++) { vPreSum.emplace_back(vPreSum.back() + vCount[i]); } C1097Int<> iiRet; for (int i = 1; i <= iMax; i++) {//商 for (int j = 1; j * i <= iMax; j++) {//除数 const long long llCount = vPreSum[min((i + 1) * j,iMax+1)] - vPreSum[i * j]; iiRet += C1097Int<>(i * llCountvCount[j]); } } return iiRet.ToInt(); } };
测试用例
template void Assert(const vector& v1, const vector& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { assert(v1[i] == v2[i]); } } template void Assert(const T& t1, const T& t2) { assert(t1 == t2); } int main() { vector nums; int res; { nums = {2, 5, 9}; Solution slu; auto res = slu.sumOfFlooredPairs(nums); Assert(10, res); } { nums = { 7, 7, 7, 7, 7, 7, 7 }; Solution slu; auto res = slu.sumOfFlooredPairs(nums); Assert(49, res); } //CConsole::Out(res); }
性能优化
先枚举除数，再枚举商。如果除数的数量为0，直接忽略。速度会有提升。
class Solution { public: int sumOfFlooredPairs(vector<int>& nums) { const int iMax = *std::max_element(nums.begin(), nums.end()); vector<int> vCount(iMax + 1); for (const auto& n : nums) { vCount[n]++; } vector<int> vPreSum = { 0 };//vPreSum[i]记录值为[0,i)的数量 for (int i = 0; i <= iMax; i++) { vPreSum.emplace_back(vPreSum.back() + vCount[i]); } C1097Int<> iiRet; for (int j = 1; j <= iMax; j++) {//除数 if (0 == vCount[j]) { continue; } for (int i = 1; j * i <= iMax; i++) {//商 const long long llCount = vPreSum[min((i + 1) * j, iMax + 1)] - vPreSum[i * j]; iiRet += C1097Int<>(i * llCount * vCount[j]); } } return iiRet.ToInt(); } };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
