首页 > 其他分享 >Count Increasing Quadruplets

Count Increasing Quadruplets

时间:2023-02-02 19:45:47浏览次数:63  
标签:Count Increasing return nums text leq vector Quadruplets

Count Increasing Quadruplets

Given a 0-indexed integer array nums of size $n$ containing all numbers from $1$ to $n$, return the number of increasing quadruplets.

A quadruplet (i, j, k, l) is increasing if:

  • $0 \leq i < j < k < l < n$, and
  • $\text{nums}[i] < \text{nums}[k] < \text{nums}[j] < \text{nums}[l]$.

Example 1:

Input: nums = [1,3,2,4,5]
Output: 2
Explanation: 
- When i = 0, j = 1, k = 2, and l = 3, nums[i] < nums[k] < nums[j] < nums[l].
- When i = 0, j = 1, k = 2, and l = 4, nums[i] < nums[k] < nums[j] < nums[l]. 
There are no other quadruplets, so we return 2.

Example 2:

Input: nums = [1,2,3,4]
Output: 0
Explanation: There exists only one quadruplet with i = 0, j = 1, k = 2, l = 3, but since nums[j] < nums[k], we return 0.

Constraints:

  • $4 \leq \text{nums.length} \leq 4000$
  • $1 \leq \text{nums}[i] \leq \text{nums.length}$
  • All the integers of nums are unique. nums is a permutation.

 

解题思路

  一开始看错题了以为是求$\text{nums}[i] < \text{nums}[j] < \text{nums}[k] < \text{nums}[l]$,这个直接用树状数组就可以实现了,参考三元组

  然后想了一下不会是枚举$j$和$k$吧,结果正解就是这样做,但自己没想出来。

  暴力枚举$j$和$k$,在满足$\text{nums}[k] < \text{nums}[j]$的前提下,找到所有小于$j$的$i$且满足$\text{nums}[i] < \text{nums}[k]$,和找到所有大于$k$的$l$且满足$\text{nums}[j] < \text{nums}[l]$,参考下面的示意图:

  因此为了在枚举$j$和$k$的时候能够快速统计出来满足$i < j$且$\text{nums}[i] < \text{nums}[k]$的$i$的数量,和满足$l > k$且$\text{nums}[l] > \text{nums}[j]$的$l$的数量,这里可以先开个数组$g[x][v]$表示下标为$x$且$\text{nums}[x] = v$的数量,然后对$g$求二维前缀和,然后根据乘法原理将两部分的元素数目相乘得到答案。

  然而前缀和数组$s[i][j]$只能得到下标小于等于$i$且值小于等于$j$的元素数量,那么如何根据$s$来求得下标大于$i$且值大于$j$的元素数量呢?也就是下图的部分:

  很简单,只要根据$s$的定义减去白色的部分就行了,具体公式为 $\text{ans} = s_{n,n} - s_{i,n} - s_{n,j} + s_{i,j}$。

  AC代码如下,时间复杂度为$O(n^2)$:

 1 class Solution {
 2 public:
 3     long long countQuadruplets(vector<int>& nums) {
 4         int n = nums.size();
 5         vector<vector<int>> s(n + 1, vector<int>(n + 1));
 6         for (int i = 1; i <= n; i++) {
 7             s[i][nums[i - 1]]++;    // 统计数量
 8         }
 9         for (int i = 1; i <= n; i++) {  // 求前缀和
10             for (int j = 1; j <= n; j++) {
11                 s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
12             }
13         }
14         long long ret = 0;
15         for (int i = 1; i <= n; i++) {
16             for (int j = i + 1; j <= n; j++) {
17                 if (nums[i - 1] > nums[j - 1]) {
18                     ret += 1ll * s[i - 1][nums[j - 1] - 1] * (s[n][n] - s[j][n] - s[n][nums[i - 1]] + s[j][nums[i - 1]]);   // 两部分相乘
19                 }
20             }
21         }
22         return ret;
23     }
24 };

 

参考资料

  转化思路 前后缀分解【力扣周赛 330】:https://www.bilibili.com/video/BV1mD4y1E7QK/

标签:Count,Increasing,return,nums,text,leq,vector,Quadruplets
From: https://www.cnblogs.com/onlyblues/p/17087208.html

相关文章

  • Comptez vos bénédictions / Count your blessings
    Mercredi,1février2023Unebellesurpriseaujourd'huidelapartdeLani:unpotpourgarderdesboutsdepapier avectoutesleschosesdansnosviesquot......
  • 计数排序(Counting Sort)
    一、算法概述1.1算法分类十种常见排序算法可以分为两大类:比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排......
  • Java并发编程——CountDownLatch
    一、闭锁CountDownLatch一个同步工具类,允许一个或者多个线程一直等待,直到其他线程的操作都执行完成之后再继续往下执行。 使用场景:在一些应用场合中,需要等待某个条件达......
  • CountDownTimer [兼容5.0及之前版本]
    说明​​CountDownTimer().cancel();​​//5.0后才有效[5.0前替换系统CountDownTimer源码]/**Copyright(C)2008TheAndroidOpenSourceProject**Licensedunder......
  • count函数
    COUNT(1):统计不为NULL的记录。COUNT(*):统计所有的记录(包括NULL)。COUNT(字段):统计该"字段"不为NULL的记录。1.如果这个字段是定义为notnull的话,一行行地从记录里面读出......
  • [AGC011E] Increasing Numbers
    非常神秘。考虑一个上升数一定可以拆分成不超过九个形如\(111...(\texttt{k个1})={10^k-1\over9}\)的数之和,我们考虑用九个数\(\{a_1,a_2,...,a_9\}\)来表示一个上升......
  • 【高并发】AQS中的CountDownLatch、Semaphore与CyclicBarrier用法总结
    CountDownLatch概述同步辅助类,通过它可以阻塞当前线程。也就是说,能够实现一个线程或者多个线程一直等待,直到其他线程执行的操作完成。使用一个给定的计数器进行初始化,该......
  • 「解题报告」ARC140F ABS Permutation (Count ver.)
    洛谷题解说这题是“巨大蠢题。这是我见过的最垃圾的ARC,没有之一。”好吧,我不会做巨大蠢题。首先我们可以想到,如果\(|a_i-a_j|=m\),那么\(a_i\)和\(a_j\)一定在......
  • windows下解决机械硬盘Load_Cycle_Count过高的问题
          通常,硬盘制造商规定的Load_Cycle_Count数目上限是600,000次,要是超过300,000次就会影响到正常的读写,再多的话就差不多要报废了。windows下通过修改高级电源设......
  • CountdownEvent
    CountdownEventSystem.Threading.CountdownEventisasynchronizationprimitivethatunblocksitswaitingthreadsafterithasbeensignaledacertainnumberof......