首页 > 其他分享 >2552.统计上升四元组

2552.统计上升四元组

时间:2024-09-12 17:14:20浏览次数:12  
标签:2552 nums 示例 三元组 四元组 数组 上升 统计

题目描述:
给你一个长度为 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 是一个排列。
Related Topics
树状数组
数组
动态规划
枚举
前缀和

解题思路:
1.遍历数组,这种属于暴力求解,超时

2.如何优化这段代码呢?减少其中的复杂程度
思考:
是否可以先确定一个三元组?如果我们把每个位置作为中心,计算以这个数为中心能组成的三元组
一个数组cnt 数组用于记录每个位置 j 作为中心时,能够构成上升三元组 (i, j, k) 的数量

标签:2552,nums,示例,三元组,四元组,数组,上升,统计
From: https://www.cnblogs.com/java-cheng/p/18405833

相关文章

  • 使用cloc进行代码行数统计与分析
    cloc(CLOC全称:CountLinesofCode)是一个开源的命令行工具,用于计算项目代码中的实际代码行数,排除注释和空行。它支持多种编程语言,并且可以分析多种文件格式。cloc的主要功能:多语言支持:cloc支持超过300种编程语言,能有效识别不同语言的代码行、注释行和空行。多平台兼容:可以在Windows......
  • Snort 和 Suricata 开源代码规模解析:行数统计与对比
    Snort和Suricata作为两个知名的开源入侵检测和防御系统,它们的代码库相对庞大。Snort:Snort的代码库规模较为紧凑,随着版本的演进,代码行数逐渐增加。目前的Snort3.x版本的代码库大约有50万到60万行之间。这包括核心检测引擎、协议解析、插件扩展等多部分。Suricata:Suricata......
  • 数据处理与统计分析篇-day01-Linux基础与环境搭建
    day01-Linux基础计算机简介概述电子计算机,电脑,PC,Computer,就是由软件+硬件组成的电子设备.组成计算机硬件CPU(运算器,控制器)存储器(内存,外存)输入设备输出设备计算机软件系统软件:充当用户和计算机硬件之间的桥梁的.PC端:windows,......
  • Excel--统计类函数,COUNT函数、COUNTA函数、COUNTBLANK函数、COUNTIF函数、COUNTIFS函
    目录 COUNT函数COUNTA函数COUNTBLANK函数COUNTIF函数COUNTIFS函数SUM函数SUMIF函数SUMIFS函数AVERAGE函数AVERAGEIFS函数COUNT函数计算指定区域内中含数据的单元格的个数,结果返回包含数字单元格的数目!只能计算包含数字的单元格COUNTA函数计算指定区域内所......
  • LeetCode: 2552. 统计上升四元组 动态规划 时间复杂度O(n*n)
    2552.统计上升四元组today2552.统计上升四元组题目描述给你一个长度为n下标从0开始的整数数组nums,它包含1到n的所有数字,请你返回上升四元组的数目。如果一个四元组(i,j,k,l)满足以下条件,我们称它是上升的:0<=i<j<k<l<n且nums[i]<nums[k]<num......
  • Leetcode3265. 统计近似相等数对 I
    EverydayaLeetcode题目来源:3265.统计近似相等数对I解法1:枚举暴力枚举数组nums中下标i和j满足i<j的nums[i]和nums[j],判断它们是否近似相等。细节:先对数组nums升序排序,在判断它们是否近似相等,转成字符串进行比较,且只交换较大数的数位。代码:/**@l......
  • 6、Python如何统计序列中元素的频度
    有一个列表如下:data=['a','c','f','b','f','e','k','d','f','k']如何统计每个元素出现的次数呢?方案一:使用Listcount方法如果只要知道某一个元素出现的次数,直接使用Listcount方法就可以data=['......
  • 2563. 统计公平数对的数目
    题目链接2563.统计公平数对的数目思路排序+二分(upper_bound-lower_bound)题解链接两种方法:二分查找/三指针(Python/Java/C++/Go)关键点排序并不影响答案(数对数量未变化)时间复杂度\(O(n\logn)\)空间复杂度\(O(1)\)代码实现:classSolution:d......
  • 【Python】72行实现代码行数统计,简单实用!
    0.前言最近突然想知道自己总共写了多少行代码,于是做了这样一个小工具……1.准备工作先考虑一下希望得到的效果:Language(语言)Lines(代码行数)Size(代码文件总大小)Files(代码文件总数)A12345300KB193B2345165KB98如上,程序输出一个表格,将代码行数作为关键字......
  • du和df的统计结果为什么不一样
    今天有个人问我du和df的统计结果为什么会不同。给他解析了一番,后来想想还是写篇文章从原理上来分析分析。我们常常使用du和df来获取目录或文件系统已占用空间的情况。但它们的统计结果是不一致的,大多数时候,它们的结果相差不会很大,但有时候它们的统计结果会相差非常大。例如:####......