C++前缀和算法的应用:统计上升四元组
本文涉及的基础知识点
C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
题目
给你一个长度为 n 下标从 0 开始的整数数组 nums ,它包含 1 到 n 的所有数字,请你返回上升四元组的数目。
如果一个四元组 (i, j, k, l) 满足以下条件,我们称它是上升的:
0 <= i < j < k < l < n 且
nums[i] < nums[k] < nums[j] < nums[l] 。
示例 1:
输入:nums = [1,3,2,4,5]
输出:2
解释:
- 当 i = 0 ,j = 1 ,k = 2 且 l = 3 时,有 nums[i] < nums[k] < nums[j] < nums[l] 。
- 当 i = 0 ,j = 1 ,k = 2 且 l = 4 时,有 nums[i] < nums[k] < nums[j] < nums[l] 。
没有其他的四元组,所以我们返回 2 。
示例 2:
输入:nums = [1,2,3,4]
输出:0
解释:只存在一个四元组 i = 0 ,j = 1 ,k = 2 ,l = 3 ,但是 nums[j] < nums[k] ,所以我们返回 0 。
参数范围:
4 <= nums.length <= 4000
1 <= nums[i] <= nums.length
nums 中所有数字 互不相同 ,nums 是一个排列。
容易理解
分析
第一层循环,枚举j,第二层循环枚举k。时间复杂度O(n*n)。在通过不通过之间,用vector<vector>就通过不了,用int**勉强可以通过。分两步:
第一步 | 求前缀和 |
第二步 | 枚举j和k |
核心代码
class Solution {
public:
long long countQuadruplets(vector& nums) {
m_c = nums.size();
int** vSum = new int*[m_c + 1];//vSum[i][j]:nums[0,j)中小于等于i的个数
for (int i = 1; i <= m_c; i++)
{//计算小于i的个数
vSum[i] = new int[m_c+1];
vSum[i][0] = 0;
for (int j = 0 ; j < m_c; j++ )
{
vSum[i][j+1] = vSum[i][j] + (nums[j] <= i);
}
}
long long llRet = 0;
for (int j = 1; j < m_c; j++)
{
for (int k = j + 1; k+1 < m_c; k++)
{
if (nums[j] < nums[k])
{
continue;
}
//nums[i]范围:nums[0,j)中小于等于nums[k]的数量
const long long lessNumK = vSum[nums[k]][j];
//nums[k+1,m_c)中大于nums[j]
const long long moreNumJ = m_c - (k + 1) - (vSum[nums[j]][m_c]- vSum[nums[j]][k+1]);
llRet += lessNumK * moreNumJ;
}
}
return llRet;
}
int m_c;
};
测试用例
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()
{
Solution slu;
vector nums ;
long long res;
nums = { 1, 3, 2, 4, 5 };
res = slu.countQuadruplets(nums);
Assert(2LL, res);
nums = { 1, 2,3,4 };
res = slu.countQuadruplets(nums);
Assert(0LL, res);
nums = { 4,3,2,1 };
res = slu.countQuadruplets(nums);
Assert(0LL, res);
nums = { 4,3,2,6,5,1 };
res = slu.countQuadruplets(nums);
Assert(0LL, res);
nums = { 1,3,2,4 };
res = slu.countQuadruplets(nums);
Assert(1LL, res);
nums = { 2,1,4,3,5 };
res = slu.countQuadruplets(nums);
Assert(2LL, res);
nums.clear();
for (int i = 0; i < 4000; i++)
{
nums.emplace_back(i + 1);
}
res = slu.countQuadruplets(nums);
Assert(0LL, res);
//CConsole::Out(res);
}
性能稍强
分析
第一层循环,枚举l或k;第二层循环,枚举j。时间复杂度O(n*n),代码简洁得多,可以轻松通过。
变量解释
llRet | 所有符合条件的四元祖 |
iLessLK | nums[0,j)中小于nums[i]的数量 |
m_v132[j] | nums[0,i)中符合i,j,k的数量 |
核心代码
class Solution {
public:
long long countQuadruplets(vector<int>& nums) {
m_c = nums.size();
long long llRet = 0;
vector<long long> m_v132(m_c);//132
for (int lk = 0; lk < m_c; lk++)
{
int iLessLK = 0;
for (int j = 0; j < lk; j++)
{
if (nums[j] < nums[lk])
{
iLessLK++;
llRet += m_v132[j];
}
else
{
//iLessLK 表示[0,j)中小于nums[lk]的数,假定其索引为i,则nums[i] < nums[lk] ,nums[j] < nums[lk],故i j lk,符合前三个数i,j,k
m_v132[j] += iLessLK;
}
}
}
return llRet;
}
int m_c;
};
2月旧代码
class Solution {
public:
long long countQuadruplets(vector& nums) {
m_c = nums.size();
//vLeft[i][m] 表示nums[i]及之前的元素,小于等于m+1的个数
int vLeft[4000][4000] = { 0 };
{
for (int i = 0; i < m_c; i++)
{
if (i > 0)
{
memcpy(vLeft[i], vLeft[i - 1], sizeof(vLeft[0]));
}
for (int j = nums[i] - 1; j < m_c; j++)
{
vLeft[i][j] ++;
}
}
}
long long llRet = 0;
for (int j = 1; j + 1 < m_c; j++)
{
for (int k = j + 1; k + 1 < m_c; k++)
{
if (nums[j] <= nums[k])
{
continue;
}
const int iLeft = vLeft[j - 1][nums[k] - 1];
const int iRight = nums[j] - vLeft[k][nums[j] - 1];
llRet += vLeft[j - 1][nums[k] - 1] * (nums.size() - k - 1 - iRight);
}
}
return llRet;
};
int m_c;
};
扩展阅读
视频课程
有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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文章来源:https://www.toymoban.com/news/detail-739206.html
文章来源地址https://www.toymoban.com/news/detail-739206.html
到了这里,关于C++前缀和算法的应用:统计上升四元组的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!