LeetCode、2542. 最大子序列的分数【中等,排序+小顶堆】

2024-01-18 12:04

本文主要是介绍LeetCode、2542. 最大子序列的分数【中等,排序+小顶堆】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 前言
  • LeetCode、2542. 最大子序列的分数【中等,排序+小顶堆】
    • 题目及类型
    • 思路及代码实现
  • 资料获取


前言

博主介绍:✌目前全网粉丝2W+,csdn博客专家、Java领域优质创作者,博客之星、阿里云平台优质作者、专注于Java后端技术领域。

涵盖技术内容:Java后端、算法、分布式微服务、中间件、前端、运维、ROS等。

博主所有博客文件目录索引:博客目录索引(持续更新)

视频平台:b站-Coder长路


LeetCode、2542. 最大子序列的分数【中等,排序+小顶堆】

来源:《LeetCode 75》

题目及类型

题目链接:2542. 最大子序列的分数

类型:数据结构/树/小顶堆


思路及代码实现

思路:排序+小顶堆

  1. 对nums2进行降序排序(排序数组中的值为nums2的索引位置值)【目的:快速定位k个元素中最小的值,我们是直接由min中的最大值来开始推导】。
  2. 从排序数组的第一个元素开始,由于是顺序,每次取到的i位置,其nums2[i]都是在[i-k+1,i]中最小的,那么就可以实际就是题目中的min(nums2[i0] , nums2[i1], … ,nums2[ik - 1])。那么对于进行k个元素的和怎么计算呢?每次取到索引值,我们就直接累加这个nums1[i]到sum中,并且将这个值添加到一个小顶堆里。
  3. 每次得到一个新的i位置时,sum会累加nums1[i],同时将nums2[i]作为min(k个nums2元素)的最小值,最后计算得到结果后,再将小顶堆中的最小值移除(问这个移除是否影响到min最小值的确定,并不会原因是每次取到的nums2[i]都已经是前面范围的最小值了!所以我们也无需管移除的最小值是什么)

复杂度分析:时间复杂度O(n.logn);空间复杂度O(n)

class Solution {public long maxScore(int[] nums1, int[] nums2, int k) {int n = nums1.length;//维护k个元素的小顶堆PriorityQueue<Integer> queue = new PriorityQueue<>(k);//创建nums2数组的索引数组,并且根据nums2数组中的值降序排列的索引数组Integer[] sorteds = new Integer[n];for (int i = 0; i < n; i ++) {sorteds[i] = i;}//根据nums2的值进行降序排列Arrays.sort(sorteds, (i, j)->nums2[j]-nums2[i]);//定义一个k个值组成的sumlong sum = 0L;//首先合并k-1个元素值for (int i = 0; i < k - 1; i ++) {sum += nums1[sorteds[i]];//合并的是基于索引值的nums1数组元素queue.offer(nums1[sorteds[i]]);}long ans = 0L;//遍历剩余的所有元素,每次构成一个新的组合for (int i = k - 1; i < n; i ++) {//将当前值累加,并将当前值添加到sum += nums1[sorteds[i]];queue.offer(nums1[sorteds[i]]);//sum即为k个元素之和   nums2[sorteds[i]]则为k个中最小的值ans = Math.max(ans, sum * nums2[sorteds[i]]);//出小顶堆中最小的元素sum -= queue.poll();}return ans;}
}

image-20240117195726842

资料获取

大家点赞、收藏、关注、评论啦~

精彩专栏推荐订阅:在下方专栏👇🏻

  • 长路-文章目录汇总(算法、后端Java、前端、运维技术导航):博主所有博客导航索引汇总
  • 开源项目Studio-Vue—校园工作室管理系统(含前后台,SpringBoot+Vue):博主个人独立项目,包含详细部署上线视频,已开源
  • 学习与生活-专栏:可以了解博主的学习历程
  • 算法专栏:算法收录

更多博客与资料可查看👇🏻获取联系方式👇🏻,🍅文末获取开发资源及更多资源博客获取🍅


整理者:长路 整理时间:2024.1.17

这篇关于LeetCode、2542. 最大子序列的分数【中等,排序+小顶堆】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/618925

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时

uva 10131 最长子序列

题意: 给大象的体重和智商,求体重按从大到小,智商从高到低的最长子序列,并输出路径。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vect

poj 3723 kruscal,反边取最大生成树。

题意: 需要征募女兵N人,男兵M人。 每征募一个人需要花费10000美元,但是如果已经招募的人中有一些关系亲密的人,那么可以少花一些钱。 给出若干的男女之间的1~9999之间的亲密关系度,征募某个人的费用是10000 - (已经征募的人中和自己的亲密度的最大值)。 要求通过适当的招募顺序使得征募所有人的费用最小。 解析: 先设想无向图,在征募某个人a时,如果使用了a和b之间的关系

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

poj 3258 二分最小值最大

题意: 有一些石头排成一条线,第一个和最后一个不能去掉。 其余的共可以去掉m块,要使去掉后石头间距的最小值最大。 解析: 二分石头,最小值最大。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <c

poj 2175 最小费用最大流TLE

题意: 一条街上有n个大楼,坐标为xi,yi,bi个人在里面工作。 然后防空洞的坐标为pj,qj,可以容纳cj个人。 从大楼i中的人到防空洞j去避难所需的时间为 abs(xi - pi) + (yi - qi) + 1。 现在设计了一个避难计划,指定从大楼i到防空洞j避难的人数 eij。 判断如果按照原计划进行,所有人避难所用的时间总和是不是最小的。 若是,输出“OPETIMAL",若

poj 2135 有流量限制的最小费用最大流

题意: 农场里有n块地,其中约翰的家在1号地,二n号地有个很大的仓库。 农场有M条道路(双向),道路i连接着ai号地和bi号地,长度为ci。 约翰希望按照从家里出发,经过若干块地后到达仓库,然后再返回家中的顺序带朋友参观。 如果要求往返不能经过同一条路两次,求参观路线总长度的最小值。 解析: 如果只考虑去或者回的情况,问题只不过是无向图中两点之间的最短路问题。 但是现在要去要回