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
第一步求前缀和第二步枚举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所有符合条件的四元祖iLessLKnums[0,j)中小于nums[i]的数量m_v132[j]nums[0,i)中符合i,j,k的数量
核心代码
class Solution {
public:
long long countQuadruplets(vector
m_c = nums.size();
long long llRet = 0;
vector
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
相关阅读
您阅读本篇文章共花了：
发表评论