【前缀和]LeetCode1862：向下取整数对和

本文涉及的基础知识点

C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频

作者推荐

动态规划LeetCode2552：优化了6版的1324模式

题目

给你一个整数数组 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

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛