LeetCode、2462. 雇佣 K 位工人的总代价【中等,最小堆+双指针】

这篇具有很好参考价值的文章主要介绍了LeetCode、2462. 雇佣 K 位工人的总代价【中等,最小堆+双指针】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言

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

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

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

视频平台:b站-Coder长路


LeetCode、2462. 雇佣 K 位工人的总代价【中等,最小堆+双指针】

来源:LeetCode专题《LeetCode 75》

题目及类型

题目链接:LeetCode、2462. 雇佣 K 位工人的总代价

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


思路及代码实现

思路:双指针+最小堆

首先理解题意,有三个传参:costs、k、candidates。

其中costs中表示有n个工人的代价、k表示我们要选拔k轮,每轮选拔1个人、candidates则是每一轮在costs中的前candidates人与最后candidates人中去挑选一个最小代价,最终我们要找到k个最小代价的和。【注:若是前candidates与后candidates人当中价值相同,那么我们应该取索引最小的】

抽象上来看,每一轮我们应该取得指定candidates*2中的一个最小代价,同时这个最小代价应该是先比较基于值,相同则是索引。有工人的数量是n个,范围为10万,那么就是在每一轮中要取得一个最小代价,想要使用n*logn时间复杂度的,我们借助最小堆来解决。

最小堆中,我们使用一个数组来表示是分别存储的是值、索引、左右,每次移出一个最小元素时,我们可以得知是左边还是右边,最终再设置左右边界值,那么我们就可以每次去根据出堆的元素来判断添加入堆的元素是左边开始还是右边开始的。

代码

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

class Solution {
    public long totalCost(int[] costs, int k, int candidates) {
        int n = costs.length;
        //维护一个优先队列 队列数组元素:元素值,索引,左右(左0右1)
        PriorityQueue<int[]> queue = new PriorityQueue<>(candidates * 2, (o1, o2) -> {
            //优先比较值,若是值相等比较索引
            if (o1[0] == o2[0]) {
                return o1[1] - o2[1];
            }
            return o1[0] - o2[0];
        });
        //遍历所有的序列(优先将前candidates、后candidates添加)
        for (int i = 0; i < n; i ++) {
            if (i < candidates || i >= n - candidates) {
                queue.offer(new int[]{costs[i], i, i < candidates ? 0 : 1});
            }
        }
        //设置左右端点
        int left = candidates - 1, right = n - candidates;
        long sum = 0L;
        //进行k轮
        for (int i = 0; i < k; i ++) {
            //出最小元素
            int[] numArr = queue.poll();
            sum += numArr[0];//数组中第一元素是数值
            //若是当前已经完全将所有元素添加到小顶堆时
            if (left >= right - 1) continue;
            //根据左右来进行补充
            if (numArr[2] == 0) {
                left ++;
                queue.offer(new int[]{costs[left], left, 0});
            }else {
                right --;
                queue.offer(new int[]{costs[right], right, 1});
            }
        }
        return sum;
    }
}

LeetCode、2462. 雇佣 K 位工人的总代价【中等,最小堆+双指针】,# LeetCode,leetcode,算法,职场和发展


资料获取

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

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

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

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


整理者:长路 整理时间:2024.1.18文章来源地址https://www.toymoban.com/news/detail-804399.html

到了这里,关于LeetCode、2462. 雇佣 K 位工人的总代价【中等,最小堆+双指针】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 最小(代价)生成树—Prim算法与Kruskal算法

    目录  一、最小生成树的特点 二、最小生成树算法  ① Prim(普里姆)算法 ②Kruskal(克鲁斯卡尔)算法  ③Prim算法与Kruskal算法对比 最小生成树是带权连通图G=(V,E)的生成树中边的权值之和最小的那棵生成树。它具有以下特点: 图G中各边权值互不相等时有唯一的最小生成树。图

    2024年02月01日
    浏览(36)
  • 【并集查找 图论 位运算】3108. 带权图里旅途的最小代价

    算法可以发掘本质,如: 一,若干师傅和徒弟互有好感,有好感的师徒可以结对学习。师傅和徒弟都只能参加一个对子。如何让对子最多。 二,有无限多1X2和2X1的骨牌,某个棋盘若干格子坏了,如何在没有坏的格子放足够多骨牌。 三,某个单色图,1表示前前景,0表示后景

    2024年04月15日
    浏览(34)
  • 【前缀和】【单调栈】LeetCode2281:巫师的总力量和

    map|动态规划|单调栈|LeetCode975:奇偶跳 单调栈分类、封装和总结 C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 作为国王的统治者,你有一支巫师军队听你指挥。 给你一个下标从 0 开始的整数数组 strength ,其中 strength[i] 表示第 i 位巫师的力量值

    2024年02月02日
    浏览(29)
  • ​LeetCode解法汇总2385. 感染二叉树需要的总时间

    https://github.com/September26/java-algorithms 给你一棵二叉树的根节点  root  ,二叉树中节点的值  互不相同  。另给你一个整数  start  。在第  0  分钟, 感染  将会从值为  start  的节点开始爆发。 每分钟,如果节点满足以下全部条件,就会被感染: 节点此前还没有感染。 节点

    2024年04月24日
    浏览(42)
  • 2304. 网格中的最小路径代价 : 从「图论最短路」过渡到「O(1) 空间的原地模拟」

    这是 LeetCode 上的 「2304. 网格中的最小路径代价」 ,难度为 「中等」 。 Tag : 「最短路」、「图」、「模拟」、「序列 DP」、「动态规划」 给你一个下标从 0 开始的整数矩阵 grid ,矩阵大小为 m x n ,由从 0 到 的不同整数组成。 你可以在此矩阵中,从一个单元格移动到下一行

    2024年01月23日
    浏览(49)
  • 1347. 制造字母异位词的最小步骤数 (中等,Counter)

    闲来无事,今天多做一题 条件很宽,可以任意替换,且排列相同也可以 所以只要统计每个字母在 s 中比在 t 中多出现的次数之和即可 学习 python 求字符的 ASCII码 需要使用内置函数 ord() python 有一个collections.Counter模块,它可以直接统计一个字符串中字符出现的次数,且它返回

    2024年02月07日
    浏览(44)
  • 【LeetCode-中等题】78. 子集

    1、子集去重版本 2、组合非去重版本 3、组合去重版本 注意:这里的nums数组里面的元素是各不相同的,所以不存在去重操作 参考讲解视频:回溯算法解决子集问题,树上节点都是目标集和! | LeetCode:78.子集 根据nums[1,2,3] 可以画出树图,收获的结果集为所有节点,并且根据

    2024年02月09日
    浏览(28)
  • Leetcode—22.括号生成【中等】

    之后我会持续更新,如果喜欢我的文章,请记得一键三连哦,点赞关注收藏,你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 !!!↖(▔▽▔)↗感谢支持!

    2024年01月23日
    浏览(74)
  • 【LeetCode-中等题】46. 全排列

    1、子集去重版本 2、组合去重版本 3、子集非去重版本 这题中nums中的数各不相同,所以不需要去重: 而下面这题,nums中的数会存在重复值,就需要去重: 参考讲解视频:代码随想录—全排列不去重版本 关键在于递归之后还要还原做回溯动作: 所以最后,我们统计到的res才

    2024年02月09日
    浏览(49)
  • 【LeetCode-中等题】79. 单词搜索

    需要一个标记数组 来标志格子字符是否被使用过了 先找到word 的第一个字符在表格中的位置,再开始递归 递归的结束条件是如果word递归到了最后一个字符了,说明能在矩阵中找到单词 剪枝条件 就是如果已经找到单词了 res = true 了 后面就不需要递归了,还有如果下标越界、

    2024年02月09日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包