首页 > 其他分享 >2389. 和有限的最长子序列

2389. 和有限的最长子序列

时间:2023-04-08 23:33:45浏览次数:55  
标签:nums int 复杂度 长子 序列 vector queries 2389 size

题目链接:2389. 和有限的最长子序列

方法:前缀和 + 二分查找

解题思路

  1. 根据题意,子序列与\(nums\)数组的元素顺序无关,因此可以先对\(nums\)从小到大排序,并计算前缀和\(nums[i] += nums[i - 1]\),此时的\(nums[i]\)表示原来nums数组\([0, i]\)的区间和。
  2. 那么\(answer[i] = idx + 1\),其中\(idx\)为满足\(nums[idx] <= queries[i]\)的\(nums\)中的最靠后坐标。则此时就变为在\(nums\)数组中找第一个大于\(queries[i]\)的下标。

代码

class Solution {
public:
    vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
        int m = queries.size();
        vector<int> ans(m);
        sort(nums.begin(), nums.end());
        for (int i = 1; i < nums.size(); i ++ ) nums[i] += nums[i - 1];
        for (int i = 0; i < m; i ++ ) ans[i] = upper_bound(nums.begin(), nums.end(), queries[i]) - nums.begin();
        return ans;
    }
};

复杂度分析

时间复杂度:\(O((n + m)logn),n = nums.size(), m = queries.size()\);
空间复杂度:\(O(1)\)。

标签:nums,int,复杂度,长子,序列,vector,queries,2389,size
From: https://www.cnblogs.com/lxycoding/p/17299581.html

相关文章

  • 自定义序列化器类
    @Serialization是一个自定义装饰器,通常用于序列化Python对象。使用@Serialization装饰器可以将一个类转换为可序列化的对象,这样就可以将其存储到文件或通过网络传输。下面是一个使用@Serialization装饰器的示例:importjsondefSerialization(cls):defserializ......
  • 颜色分类(数组、双指针)、排列序列(递归、数学)、合并区间(数组、排序)
    颜色分类(数组、双指针)给定一个包含红色、白色和蓝色,一共n__个元素的数组,**原地(https://baike.baidu.com/item/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95)**对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。此题中,我们使用整数0、1和2分别表示红色、......
  • 7个最新的时间序列分析库介绍和代码示例
    时间序列分析包括检查随着时间推移收集的数据点,目的是确定可以为未来预测提供信息的模式和趋势。我们已经介绍过很多个时间序列分析库了,但是随着时间推移,新的库和更新也在不断的出现,所以本文将分享8个目前比较常用的,用于处理时间序列问题的Python库。他们是tsfresh,autots,darts......
  • R语言EG(Engle-Granger)两步法协整检验、RESET、格兰杰因果检验、VAR模型分析CPI和PPI
    全文链接:http://tecdat.cn/?p=31108最近我们被客户要求撰写关于VAR模型的研究报告,包括一些图形和统计输出。作为衡量通货膨胀的基本指标,消费者价格指数CPI和生产者价格指数PPI的作用关系与传导机制一直是宏观经济研究的核心问题。对此问题的研究显然具有重要的学术价值与现实意......
  • 经济学:动态模型平均(DMA)、动态模型选择(DMS)、ARIMA、TVP预测原油时间序列价格|附代
    全文链接:http://tecdat.cn/?p=22458最近我们被客户要求撰写关于动态模型平均的研究报告,包括一些图形和统计输出。本文提供了一个经济案例。着重于原油市场的例子。简要地提供了在经济学中使用模型平均和贝叶斯方法的论据,使用了动态模型平均法(DMA),并与ARIMA、TVP等方法进行比较简......
  • 极值分析:分块极大值BLOCK-MAXIMA、阈值超额法、广义帕累托分布GPD拟合降雨数据时间序
    全文链接:http://tecdat.cn/?p=25348最近我们被客户要求撰写关于极值分析的研究报告,包括一些图形和统计输出。你们可能知道,实际极值分析有两种常用方法:分块极大值Block-maxima、阈值超额法thresholdexcess今天,我们将分别介绍这两种方法。分块极大值Block-maxima分块样本极大......
  • acwing2816. 判断子序列
    linkcode#include<bits/stdc++.h>usingnamespacestd;constintN=100010;inta[N],b[N];intmain(){ intn,m; cin>>n>>m; for(inti=1;i<=n;i++)cin>>a[i]; for(inti=1;i<=m;i++)cin>>b[i]; in......
  • 106. 从中序与后序遍历序列构造二叉树 105. 从前序与中序遍历序列构造二叉树
    给定两个整数数组inorder和postorder,其中inorder是二叉树的中序遍历,postorder是同一棵树的后序遍历,请你构造并返回这颗二叉树。classSolution{public:TreeNode*buildTree(vector<int>&inorder,vector<int>&postorder){if(postorder.size()==0)......
  • 记spring-security升级,引发的redis反序列化不一致问题
    问题解决参考文章如下:https://my.oschina.net/klblog/blog/5559133https://blog.csdn.net/qq_37421368/article/details/124850449问题复现由于一些原因,登录的token由旧版本的微服务存入的redis,另一个新版本的微服务需要取出数据校验springboot版本升级导致spring-secu......
  • [蓝桥杯 2021 国 AB] 翻转括号序列(线段树上二分)
    [蓝桥杯2021国AB]翻转括号序列题目描述给定一个长度为\(n\)的括号序列,要求支持两种操作:将\(\left[L_{i},R_{i}\right]\)区间内(序列中的第\(L_{i}\)个字符到第\(R_{i}\)个字符)的括号全部翻转(左括号变成右括号,右括号变成左括号)。求出以\(L_{i}\)为左端点......