计算增加的四元组数量

2025年2月7日 | 10分钟阅读

问题陈述

在本问题描述中，给定一个大小为 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

说明

nums = [1, 3, 2, 4, 5]。

遍历数组中的每个元素

对于 nums[0] = 1

遍历其后的所有元素
对于 nums[1] = 3
遍历其后的所有元素
对于 nums[3] = 4, nums[4] = 5
条件 nums[i] < nums[j] < nums[k] < nums[l] 得到满足。

增加计数。

对于 nums[1] = 3

遍历其后的所有元素
对于 nums[3] = 4, nums[4] = 5

条件 nums[i] < nums[j] < nums[k] < nums[l] 得到满足。

增加计数

总递增四元组数: 2。

因此，输出为 2。

示例 2

输入: nums = [1,2,3,4]

输出 0

说明

nums = [1, 2, 3, 4]，没有递增四元组。

递增四元组的给定条件是 nums[i] < nums[j] < nums[k] < nums[l]，其中 i < j < k < l。

在这个数组中，不存在这样的四元组，因为元素已经按递增顺序排列，并且没有四个元素满足给定条件。

因此，输出为 0。

Java 暴力解法

import java. util.Scanner; 
public class Solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); 
        // Input the length of the array
System.out.println("Enter the length of the array:");
        int n = scanner.nextInt();
        // Input the array elements
System.out.println("Enter the array elements separated by space:");
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        // Output the result of countQuadruplets method
System.out.println("Number of quadruplets: " + countQuadruplets(nums)); 
scanner.close();
    }
    // Method to count the number of quadruplets satisfying the condition
    public static long countQuadruplets(int[] nums) {
        int n = nums.length;
        long[] cnt = new long[n];
        long ans = 0;
        for (int j = 0; j < n; j++) {
            int prev_small = 0;
            for (int i = 0; i < j; i++) {
                if (nums[j] > nums[i]) {
prev_small++;
ans += cnt[i];
                } else if (nums[j] < nums[i]) {
cnt[i] += prev_small;
                }
            }
        }
        return ans;
    }
}

输出

代码解释

初始化变量

初始化 n 为数组 nums 的长度。
初始化一个类型为 long 的数组 cnt，长度与 nums 相同，用于存储较小元素的计数。
初始化 ans（答案）为 0。

遍历数组

对于索引 j 处的每个元素 nums[j]

初始化 prev_small 为 0。
从 0 迭代到 j-1，考虑 nums[j] 之前的所有元素。

在此内部循环中

如果 nums[j] 大于 nums[i]，这意味着 nums[j] 与 nums[0] 到 nums[i] 的所有元素形成一个四元组。递增 prev_small 以跟踪 nums[j] 之前较小元素的计数，并将 cnt[i]（其中包含 nums[i] 之前较小元素的计数）添加到 ans 中。
如果 nums[j] 小于 nums[i]，这意味着 nums[i] 与 nums[j] 和 nums[j] 之前所有较小的元素形成一个四元组。通过 prev_small 递增 cnt[i] 以跟踪此类事件。

返回 ans，其中包含满足条件的四元组的计数。

时间复杂度

countQuadruplets 方法在最坏情况下的时间复杂度为 O(n^2)。其中 n 表示输入数组的大小。这是因为该方法迭代数组两次：从外部循环到内部循环。

空间复杂度

空间复杂度为 O(n)，因为辅助 cnt 数组与输入数组大小相同。空间复杂度与输入数组的大小成正比。

Java 优化方法

import java. util.Scanner; 
public class Solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); 
        // Input the length of the array
System.out.println("Enter the length of the array:");
        int n = scanner.nextInt();
        // Input the array elements
System.out.println("Enter the array elements separated by space:");
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        // Output the result of countQuadruplets method
        Solution solution = new Solution();
System.out.println("Number of quadruplets: " + solution.countQuadruplets(nums)); 
scanner.close();
    }
    // Method to count the number of quadruplets in the array
    public long countQuadruplets(int[] nums) {
        int n = nums.length;
        Fenwick t1 = new Fenwick(new int[n + 1]); // Initialize Fenwick tree for range queries
        Fenwick t2 = new Fenwick(new int[n + 1]); // Initialize Fenwick tree for point updates
        long ans = 0; // Initialize the answer counter
        for (int i = 1; i <= n; i++) {
           
t2.update(i, 1); // Initially, all elements are present
        }
        for (int j = 0; j < n; j++) {
t2.update(nums[j], -1); // Mark nums[j] as visited
            for (int k = j + 1; k < n; k++) {
t2.update(nums[k], -1); // Mark nums[k] as visited
                if (nums[j] > nums[k]) {
long c1 = t1.query(1, nums[k]); // Count of elements less than nums[k] before index j
long c2 = t2.query(nums[j], n); // Count of elements greater than nums[j] after index k
ans += (c1 * c2); // Update the answer
                }
            }
            for (int k = j + 1; k < n; k++) {   
t2.update(nums[k], 1); // Reset the Fenwick tree for the next iteration
            }
t1.update(nums[j], 1); // Mark nums[j] as visited
        }
        return ans;
    }
}
// Fenwick tree class for range queries and point updates
class Fenwick {
    long[] bit; // Binary indexed tree
    // Constructor to initialize the Fenwick tree
    public Fenwick(int arr[]) {
        bit = new long[arr.length]; // Initialize the bit array
        for (int i = 1; i < arr.length; i++) {
            update(i, arr[i]); // Update the Fenwick tree
        }
    }
    // Method to calculate the prefix sum up to a given index
    public long sum(int index) {
        long sum = 0; // Initialize the sum
        while (index > 0) {
            sum += bit[index]; // Add the value at the current index to the sum
            index = index - (index & -index); // Move to the parent index
        }
        return sum; // Return the sum
    }
    // Method to calculate the sum of elements in a given range
    public long query(int l, int r) {
        r = Math.min(r, bit.length - 1); // Adjust the right index
        l = Math.max(l, 1); // Adjust the left index
        return sum(r) - sum(l - 1); // Return the sum of elements in the range [l, r]
    }
    // Method to update the value of a specific index
    public void update(int index, int val) {
        while (index < bit.length) {
            bit[index] += val; // Update the value at the current index
            index = index + (index & -index); // Move to the next index
        }
    }
}

输出

代码解释

计算四元组方法

初始化数组长度 n。
初始化两棵 Fenwick 树：t1 用于范围查询，t2 用于点更新。
初始化答案计数器 ans。
将 t2 的所有元素初始化为 1，以标记所有元素最初都存在。

遍历数组元素

更新 t2 以将当前元素标记为已访问。
遍历当前元素之后的元素
更新 t2 以将下一个元素标记为已访问。
如果当前元素大于下一个元素
使用 t1 计算当前索引之前小于下一个元素的元素数量。
使用 t2 计算下一个索引之后大于当前元素的元素数量。
通过将这些计数相乘来更新答案。
为下一次迭代重置 t2。
在 t1 中将当前元素标记为已访问。
返回最终答案。

Fenwick 树类

使用给定数组初始化 Fenwick 树。
计算到给定索引的前缀和。
计算给定范围内的元素和。
更新特定索引的值。

时间复杂度

countQuadruplelets 方法的时间复杂度为 O(n^2 * log n)，这是由于嵌套循环的使用以及其中对数运算的结果。
Fenwick 树中的更新和查询操作对 n 具有对数复杂度，并且它们在数组的每个值中同时执行。

空间复杂度

这里的空间复杂度为 O(n)，它基于两棵大小为 n+1 的 Fenwick 树 t1 和 t2。
从变量和常量的其余部分位于内存空间的角度来看，它们不会增加复杂度空间。

Java 前缀和方法

import java. util.Scanner; 
public class Solution {
    public long countQuadruplets(int[] nums) {
        int[][] preGra = new int[nums. length][nums.length];
        int[][] preLess = new int[nums.length][nums.length]; 
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (nums[j] > nums[i]) {
preGra[i][j]++;
                }
                if (nums[j] < nums[i]) {
preLess[i][j]++;
                }
            }
            for (int j = 1; j < nums.length; j++) {  
preGra[i][j] += preGra[i][j - 1];        
preLess[i][j] += preLess[i][j - 1];
            }
        }
        long res = 0;
        for (int i = 1; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                if (nums[j] < nums[i]) {
long v = preLess[j][i];
                    v *= (long) (preGra[i][nums.length - 1] - preGra[i][j]); 
res += v;
                }
            }
        }
        return res;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
System. out.println("Enter the length of the array:");
        int n = scanner.nextInt();
        int[] nums = new int[n];
System.out.println("Enter the array elements:");
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        Solution solution = new Solution();
        long result = solution.countQuadruplets(nums); 
System. out.println("Number of quadruplets: " + result);
scanner.close();
    }
}

输出

代码解释

计算四元组的方法

初始化两个 2D 数组 preGra 和 preLess，用于存储输入数组中大于和小于每个元素的数字计数。
通过比较输入数组中的每对元素来填充 preGra 和 preLess 数组。
计算 preGra 和 preLess 数组的前缀和，以提高后续计算效率。
遍历输入数组中的元素对，以计算满足条件的四元组数量。

填充 preGra 和 preLess 数组

对于每个元素 nums[i]
遍历输入数组中的所有元素。
如果 nums[j] 大于 nums[i]，则递增 preGra[i][j]。
如果 nums[j] 小于 nums[i]，则递增 preLess[i][j]。
计算 preGra 和 preLess 数组的前缀和。

计算四元组

遍历输入数组中的元素对（i 和 j）
如果 nums[j] 小于 nums[i]，则计算满足条件的四元组数量。
将 preLess[j][i] 乘以大于 nums[i] 的数字计数与大于 nums[j] 的数字计数之差（从 preGra 计算）。
将此计数添加到结果中。

时间复杂度

运行时间复杂度为 O(n^2)，其中 n 是给定数组长度的大小。这种复杂度是由于使用嵌套循环来确定当前元素等于给定元素的更大和更小的元素。

空间复杂度

空间复杂度遵循 O(n^2) 顺序集。这是因为所需信息存储在大小为 n x n 的 2D 数组中，其中数组中的每个元素分别是小于和大于它的所有元素的计数。此外，它还包含一些用于内部函数变量的位。这些位是恒定的空间开销。

Java 动态规划方法

import java. util.Scanner; 
public class Solution {
    public long countQuadruplets(int[] nums) {
        int dp[][] = new int[nums.length][nums.length + 1]; 
        for (int i = 0; i < dp.length; i++) {
            if (i - 1 >= 0) {
                for (int j = 1; j <= nums.length; j++) {
dp[i][j] += dp[i - 1][j];
                }
            }
            for (int j = nums[i]; j <= nums.length; j++) {
dp[i][j]++;
            }
        }
        int dp2[][] = new int[nums.length][nums.length + 1]; 
        for (int i = dp2.length - 1; i >= 0; i--) {
            if (i + 1 < dp2.length) {
                for (int j = nums.length; j >= 1; j--) {
                    if (i + 1 <= nums.length) {
dp2[i][j] += dp2[i + 1][j];
                    }
                }
            }
            for (int j = 1; j <= nums[i]; j++) {  
dp2[i][j]++;
            }
        }
        long sum = 0; 
        for (int j = 0; j < nums.length; j++) {
            for (int k = j + 1; k < nums.length; k++) {
                if (nums[j] > nums[k]) {
                    if (j - 1 >= 0 && k + 1 < nums.length) {      
sum += dp[j - 1][nums[k]] * dp2[k + 1][nums[j]];
                    }
                }
            }
        }
        return sum;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); 
System.out.println("Enter the length of the array:");
        int n = scanner.nextInt();
        int[] nums = new int[n]; 
System.out.println("Enter the elements of the array:");
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        Solution solution = new Solution();
System.out.println("Number of quadruplets: " + solution.countQuadruplets(nums)); 
scanner.close();
    }
}

输出

代码解释

计算四元组的方法

初始化一个 2D 数组 dp，用于存储小于或等于当前元素的元素计数。

遍历输入数组中的每个元素

如果当前索引 i 大于 0，则将前一行的计数复制到当前行。
递增当前行中大于当前元素的元素的计数。

初始化另一个 2D 数组 dp2，用于存储大于或等于当前元素的元素计数。

以相反顺序遍历输入数组中的每个元素

如果当前索引 i 小于 nums.length - 1，则将下一行的计数复制到当前行。
递增当前行中小于当前元素的元素的计数。

遍历输入数组中的元素对

如果第一个元素大于第二个元素
如果 dp 和 dp2 存在有效索引，则计算此对对总计数的贡献

时间复杂度

该算法对输入数组 nums 进行两次读取，因此时间复杂度变为 O(n^2)，其中 n 是 nums 的长度。在每次遍历中，它执行两次 2D 数组更新：dp 和 dp2。
这些操作每次需要 O(n^2) 时间。就像初始阶段一样，第四步也增加了 O(n^2) 次操作。在这种情况下，算法以二次时间运行，复杂度为 O(n^2)。

空间复杂度

该算法使用大小为 n x (n-1) 的 2D dp 和 dp2 数组，因此空间复杂度为 O(n^2)。
此外，它还使用额外的变量和数据结构。它所需的常量或线性空间保持不变。
因此，空间复杂度变为 O(n^2)，与嵌套循环的复杂度相同。

下一个主题Cpp-program-to-find-the-length-of-the-maximum-non-decreasing-subsegment

← 上一个下一个 →

计算增加的四元组数量

问题陈述

示例 1

说明

示例 2

说明

Java 暴力解法

代码解释

时间复杂度

空间复杂度

Java 优化方法

代码解释

时间复杂度

空间复杂度

Java 前缀和方法

代码解释

时间复杂度

空间复杂度

Java 动态规划方法

代码解释

时间复杂度

空间复杂度

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

计算增加的四元组数量

问题陈述

示例 1

说明

示例 2

说明

Java 暴力解法

代码解释

时间复杂度

空间复杂度

Java 优化方法

代码解释

时间复杂度

空间复杂度

Java 前缀和方法

代码解释

时间复杂度

空间复杂度

Java 动态规划方法

代码解释

时间复杂度

空间复杂度

相关帖子

RSS 链表

合并两棵二叉树

合并两个二叉最大堆

构建堆的时间复杂度

多路树在数据结构中的应用

检查一个队列是否可以使用一个栈排序到另一个队列

访问数组位置以最大化分数

循环链表的有序插入

DS 中的垃圾回收

检查两棵二叉树是否互为镜像

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器