class Solution {
public:
long long countQuadruplets(vector<int>& nums) {
}
};
6340. 统计上升四元组
给你一个长度为 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 <= 40001 <= nums[i] <= nums.lengthnums 中所有数字 互不相同 ，nums 是一个排列。原站题解
cpp 解法, 执行用时: 106 ms, 内存消耗: 14.4 MB, 提交时间: 2024-09-10 09:14:46
class Solution {
public:
typedef long long ll;
long long countQuadruplets(vector<int> &nums) {
int n=nums.size();
ll sum=0;
vector<ll>v(n);//132
for(int i=0;i<n;i++){
int z=0;
for(int j=0;j<i;j++){
if(nums[i]>nums[j]){
sum+=v[j];
z++;
}else{
v[j]+=z;
}
}
}
return sum;
}
};
cpp 解法, 执行用时: 1072 ms, 内存消耗: 78.9 MB, 提交时间: 2023-01-30 11:40:07
class Solution {
int great[4000][4001];
public:
long long countQuadruplets(vector<int> &nums) {
int n = nums.size();
for (int k = n - 2; k; k--) {
memcpy(great[k], great[k + 1], sizeof(great[k + 1]));
for (int x = nums[k + 1] - 1; x > 0; x--)
great[k][x]++;
}
long ans = 0;
for (int j = 1; j < n - 2; j++)
for (int k = j + 1; k < n - 1; k++)
if (int x = nums[k]; nums[j] > x)
ans += (x - n + 1 + j + great[j][x]) * great[k][nums[j]];
return ans;
}
};
python3 解法, 执行用时: 4276 ms, 内存消耗: 350.6 MB, 提交时间: 2023-01-30 11:39:45
class Solution:
def countQuadruplets(self, nums: List[int]) -> int:
n = len(nums)
great = [0] * n
great[-1] = [0] * (n + 1)
for k in range(n - 2, 0, -1):
great[k] = great[k + 1][:]
for x in range(1, nums[k + 1]):
great[k][x] += 1
ans = 0
for j in range(1, n - 1):
for k in range(j + 1, n - 1):
x = nums[k]
if nums[j] > x:
ans += (x - n + 1 + j + great[j][x]) * great[k][nums[j]]
return ans
java 解法, 执行用时: 122 ms, 内存消耗: 214.7 MB, 提交时间: 2023-01-30 11:39:30
class Solution {
public long countQuadruplets(int[] nums) {
int n = nums.length;
int[][] great = new int[n][n + 1];
for (int k = n - 2; k > 0; k--) {
great[k] = great[k + 1].clone();
for (int x = nums[k + 1] - 1; x > 0; x--)
great[k][x]++;
}
long ans = 0;
for (int j = 1; j < n - 2; j++)
for (int k = j + 1; k < n - 1; k++) {
int x = nums[k];
if (nums[j] > x)
ans += (x - n + 1 + j + great[j][x]) * great[k][nums[j]];
}
return ans;
}
}
golang 解法, 执行用时: 120 ms, 内存消耗: 165 MB, 提交时间: 2023-01-30 11:39:12
func countQuadruplets(nums []int) (ans int64) {
n := len(nums)
great := make([][]int, n)
great[n-1] = make([]int, n+1)
for k := n - 2; k > 0; k-- {
great[k] = append([]int(nil), great[k+1]...)
for x := nums[k+1] - 1; x > 0; x-- {
great[k][x]++
}
}
for j := 1; j < n-2; j++ {
for k := j + 1; k < n-1; k++ {
x := nums[k]
if nums[j] > x {
ans += int64((x - n + 1 + j + great[j][x]) * great[k][nums[j]])
}
}
}
return
}
golang 解法, 执行用时: 112 ms, 内存消耗: 165 MB, 提交时间: 2023-01-30 11:38:55
func countQuadruplets(nums []int) (ans int64) {
n := len(nums)
great := make([][]int, n)
great[n-1] = make([]int, n+1)
for k := n - 2; k >= 2; k-- {
great[k] = append([]int(nil), great[k+1]...)
for x := nums[k+1] - 1; x > 0; x-- {
great[k][x]++ // x < nums[k+1]，对于 x，大于它的数的个数 +1
}
}
less := make([]int, n+1)
for j := 1; j < n-2; j++ {
for x := nums[j-1] + 1; x <= n; x++ {
less[x]++ // x > nums[j-1]，对于 x，小于它的数的个数 +1
}
for k := j + 1; k < n-1; k++ {
if nums[j] > nums[k] {
ans += int64(less[nums[k]] * great[k][nums[j]])
}
}
}
return
}
cpp 解法, 执行用时: 1068 ms, 内存消耗: 79.1 MB, 提交时间: 2023-01-30 11:38:41
class Solution {
int great[4000][4001];
public:
long long countQuadruplets(vector<int> &nums) {
int n = nums.size(), less[n + 1];
for (int k = n - 2; k >= 2; k--) {
memcpy(great[k], great[k + 1], sizeof(great[k + 1]));
for (int x = nums[k + 1] - 1; x > 0; x--)
great[k][x]++; // x < nums[k+1]，对于 x，大于它的数的个数 +1
}
long ans = 0;
memset(less, 0, sizeof(less));
for (int j = 1; j < n - 2; j++) {
for (int x = nums[j - 1] + 1; x <= n; x++)
less[x]++; // x > nums[j-1]，对于 x，小于它的数的个数 +1
for (int k = j + 1; k < n - 1; k++)
if (nums[j] > nums[k])
ans += less[nums[k]] * great[k][nums[j]];
}
return ans;
}
};
java 解法, 执行用时: 119 ms, 内存消耗: 214 MB, 提交时间: 2023-01-30 11:37:59
class Solution {
public long countQuadruplets(int[] nums) {
int n = nums.length;
int[][] great = new int[n][n + 1];
for (int k = n - 2; k >= 2; k--) {
great[k] = great[k + 1].clone();
for (int x = nums[k + 1] - 1; x > 0; x--)
great[k][x]++; // x < nums[k+1]，对于 x，大于它的数的个数 +1
}
long ans = 0;
int[] less = new int[n + 1];
for (int j = 1; j < n - 2; j++) {
for (int x = nums[j - 1] + 1; x <= n; x++)
less[x]++; // x > nums[j-1]，对于 x，小于它的数的个数 +1
for (int k = j + 1; k < n - 1; k++)
if (nums[j] > nums[k])
ans += less[nums[k]] * great[k][nums[j]];
}
return ans;
}
}
python3 解法, 执行用时: 3736 ms, 内存消耗: 351.1 MB, 提交时间: 2023-01-30 11:37:38
class Solution:
def countQuadruplets(self, nums: List[int]) -> int:
n = len(nums)
great = [0] * n
great[-1] = [0] * (n + 1)
for k in range(n - 2, 1, -1):
great[k] = great[k + 1][:]
for x in range(1, nums[k + 1]):
great[k][x] += 1 # x < nums[k+1]，对于 x，大于它的数的个数 +1
ans = 0
less = [0] * (n + 1)
for j in range(1, n - 1):
for x in range(nums[j - 1] + 1, n + 1):
less[x] += 1 # x > nums[j-1]，对于 x，小于它的数的个数 +1
for k in range(j + 1, n - 1):
if nums[j] > nums[k]:
ans += less[nums[k]] * great[k][nums[j]]
return ans