设计师培训资料,网站seo模块,海淀西北旺网站建设,都匀住房与城乡建设部网站从数量最多的堆取走礼物【LC2558】 给你一个整数数组 gifts #xff0c;表示各堆礼物的数量。每一秒#xff0c;你需要执行以下操作#xff1a; 选择礼物数量最多的那一堆。如果不止一堆都符合礼物数量最多#xff0c;从中选择任一堆即可。选中的那一堆留下平方根数量的礼物…从数量最多的堆取走礼物【LC2558】 给你一个整数数组 gifts 表示各堆礼物的数量。每一秒你需要执行以下操作 选择礼物数量最多的那一堆。如果不止一堆都符合礼物数量最多从中选择任一堆即可。选中的那一堆留下平方根数量的礼物向下取整取走其他的礼物。 返回在 k 秒后剩下的礼物数量*。* 思路 使用大顶堆存放所有礼物每次将堆顶元素移出并将其平方根放入堆中最后求出堆中剩余礼物数目 实现 class Solution {public long pickGifts(int[] gifts, int k) {long res 0L;PriorityQueueInteger pq new PriorityQueue((o1, o2) - o2 - o1);for (int gift :gifts){pq.add(gift);res gift;}while(k-- 0){int poll pq.poll(), left (int)Math.sqrt(poll);res - poll - left;pq.add(left);}return res;}
}复杂度 时间复杂度 O ( n k l o g n ) O(nklogn) O(nklogn)空间复杂度 O ( n ) O(n) O(n)
