2023-11-22：用go语言，给你一个长度为 n 下标从 0 开始的整数数组 nums。 它包含 1 到 n 的所有数字，请
2023-11-22：用go语言，给你一个长度为 n 下标从 0 开始的整数数组 nums。
它包含 1 到 n 的所有数字，请你返回上升四元组的数目。
如果一个四元组 (i, j, k, l) 满足以下条件，我们称它是上升的：
0
nums[i] < nums[k] < nums[j] < nums[l] 。
输入：nums = [1,3,2,4,5]。
输出：2。
来自左程云。
答案2023-11-22：
go代码用灵捷3.5编写。
rust代码用讯飞星火编写。
c++的代码用天工编写。
灵捷3.5本来用起来还可以，但有次数限制，故放弃。
大体过程如下：
算法1：countQuadruplets1
1.初始化变量：n为数组长度，ans为结果计数器，dp为动态规划数组。
2.遍历数组，从第二个元素开始（下标为1）：
a.初始化计数器cnt为0。
b.遍历当前元素之前的所有元素（下标小于当前元素的下标），如果当前元素大于前一个元素，则将dp[j]加到ans上，并将cnt加1。
c.再次遍历当前元素之前的所有元素（下标小于当前元素的下标），如果当前元素大于前一个元素，则将cnt加到dp[j]上；否则，将dp[j]加上cnt的整数值。
3.返回ans作为结果。
算法2：countQuadruplets2
1.初始化变量：n为数组长度，ans为结果计数器，dp为动态规划数组。
2.遍历数组，从第二个元素开始（下标为1）：
a.初始化计数器cnt为0。
b.遍历当前元素之前的所有元素（下标小于当前元素的下标），如果当前元素大于前一个元素，则将dp[j]加到ans上，并将cnt加1；否则，将dp[j]加上cnt的整数值。
3.返回ans作为结果。
总的时间复杂度：两种算法的时间复杂度都是O(n^2)，因为需要两层循环遍历数组。
总的额外空间复杂度：两种算法的空间复杂度都是O(n)，因为需要使用一个长度为n的动态规划数组dp。
go完整代码如下：
package?main
import?"fmt"
func?countQuadruplets1(nums?[]int)?int64?{
n?:=?len(nums)
var?ans?int64
dp?:=?make([]int64,?n)
for?l?:=?1;?l?
cnt?:=?0
for?j?:=?0;?j?
if?nums[j]?
ans?+=?dp[j]
}
}
cnt?=?0
for?j?:=?0;?j?
if?nums[j]?
cnt++
}?else?{
dp[j]?+=?int64(cnt)
}
}
}
return?ans
}
func?countQuadruplets2(nums?[]int)?int64?{
n?:=?len(nums)
var?ans?int64
dp?:=?make([]int64,?n)
for?l?:=?1;?l?
cnt?:=?0
for?j?:=?0;?j?
if?nums[j]?
ans?+=?dp[j]
cnt++
}?else?{
dp[j]?+=?int64(cnt)
}
}
}
return?ans
}
func?main()?{
nums?:=?[]int{1,?3,?2,?4,?5}
fmt.Println(countQuadruplets1(nums))
fmt.Println(countQuadruplets2(nums))
}
在这里插入图片描述rust完整代码如下：
fn?count_quadruplets1(nums:?Vec)?->?i64?{
let?n?=?nums.len();
let?mut?ans?=?0;
let?mut?dp?=?vec![0;?n];
for?l?in?1..n?{
let?mut?cnt?=?0;
for?j?in?0..l?{
if?nums[j]?
ans?+=?dp[j];
cnt?+=?1;
}?else?{
dp[j]?+=?cnt;
}
}
}
ans?as?i64
}
fn?count_quadruplets2(nums:?Vec)?->?i64?{
let?n?=?nums.len();
let?mut?ans?=?0;
let?mut?dp?=?vec![0;?n];
for?l?in?1..n?{
let?mut?cnt?=?0;
for?j?in?0..l?{
if?nums[j]?
ans?+=?dp[j];
cnt?+=?1;
}?else?{
dp[j]?+=?cnt;
}
}
}
ans?as?i64
}
fn?main()?{
let?nums?=?vec![1,?3,?2,?4,?5];
println!("count_quadruplets1:?{}",?count_quadruplets1(nums));
let?nums?=?vec![1,?3,?2,?4,?5];
println!("count_quadruplets2:?{}",?count_quadruplets2(nums));
}
在这里插入图片描述c++完整代码如下：
#include?
#include?
using?namespace?std;
long?long?countQuadruplets1(vector&?nums)?{
int?n?=?nums.size();
long?long?ans?=?0;
vector?dp(n,?0);
for?(int?l?=?1;?l?
for?(int?j?=?0;?j?
if?(nums[j]?
ans?+=?dp[j];
}
}
int?cnt?=?0;
for?(int?j?=?0;?j?
if?(nums[j]?
cnt++;
}
else?{
dp[j]?+=?cnt;
break;
}
}
}
return?ans;
}
long?long?countQuadruplets2(vector&?nums)?{
int?n?=?nums.size();
long?long?ans?=?0;
vector?dp(n,?0);
for?(int?l?=?1;?l?
int?cnt?=?0;
for?(int?j?=?0;?j?
if?(nums[j]?
ans?+=?dp[j];
cnt++;
}
else?{
dp[j]?+=?cnt;
}
}
}
return?ans;
}
int?main()?{
vector?nums?=?{?1,?3,?2,?4,?5?};
cout?
cout?
return?0;
}
在这里插入图片描述
- 发表于:
- 原文链接：https://page.om.qq.com/page/O0CTz67gjkMkcpULt57qrToQ0
- 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号（企鹅号）传播渠道之一，根据《腾讯内容开放平台服务协议》转载发布内容。
- 如有侵权，请联系 cloudcommunity@tencent.com 删除。
相关快讯
扫码
添加站长 进交流群
领取专属 10元无门槛券
私享最新 技术干货
腾讯云开发者
