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

简介: 【前缀和]LeetCode1862:向下取整数对和

题目

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



相关文章
|
2月前
|
存储
LeetCode整数反转
解决LeetCode上的整数反转问题的几种方法,包括错误的方法和优化后的解决方案,以及如何避免反转后的整数超出32位有符号整数范围的问题。
44 1
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
128 2
|
2月前
【LeetCode】整数翻转
【LeetCode】整数翻转
20 1
|
2月前
|
存储 C++
Leetcode第十二题(整数转罗马数字)
LeetCode第12题“整数转罗马数字”的解题方法,包括罗马数字的基本规则和特殊规则,以及如何使用C++实现整数到罗马数字的转换。
20 0
|
2月前
|
C++
Leetcode第十三题(罗马数字转整数)
这篇文章介绍了LeetCode第13题“罗马数字转整数”的解题方法,通过一个C++的类`Solution`中的`romanToInt`函数来实现,该函数使用哈希表和遍历字符串的方法,根据罗马数字的规则将输入的罗马数字字符串转换为对应的整数值。
56 0
|
2月前
|
算法 C++
Leetcode第八题(字符串转换整数(atoi))
这篇文章介绍了LeetCode上第8题“字符串转换整数(atoi)”的解题思路和C++的实现方法,包括处理前导空格、正负号、连续数字字符以及整数溢出的情况。
22 0
|
4月前
|
算法
LeetCode第12题目整数转罗马数字
该文章介绍了 LeetCode 第 12 题整数转罗马数字的解法,通过使用 TreeMap 按照整数从大到小排序,先使用大的罗马数字表示整数,再用小的,核心是先表示完大的罗马数字,想通此点该题较简单。
LeetCode第12题目整数转罗马数字
|
4月前
|
算法
LeetCode第8题字符串转换整数 (atoi)
该文章介绍了 LeetCode 第 8 题字符串转换整数 (atoi)的解法,需要对字符串进行格式解析与校验,去除前导空格和处理正负号,通过从高位到低位的计算方式将字符串转换为整数,并处理越界情况。同时总结了这几道题都需要对数字的表示有理解。
LeetCode第8题字符串转换整数 (atoi)
|
4月前
|
算法
LeetCode第7题整数反转
该文章介绍了 LeetCode 第 7 题整数反转的解法,通过除 10 取模和乘 10 累加的方式实现整数反转,同时注意边界情况的判断,并总结了通过举例推算发现规律的解题思路。
LeetCode第7题整数反转
|
4月前
|
算法
LeetCode第13题目罗马数字转整数
该文章介绍了 LeetCode 第 13 题罗马数字转整数的解法,通过从大到小解析罗马数字,根据罗马数字的特点,按照从大到小的顺序匹配罗马数字和整数的关系,从而解决该问题,同时强调要注意观察题目考查的知识点特征。