队列排序(JAVA)"/>
优先队列排序(JAVA)
执行K次最大分数_力扣每日一题
思路:执行k次,每次取出数组中的最大值,结果需要和最大值/3向上取整求和。最后返回最大值。注意:1 <= nums.length, k <= 10^5,时间复杂度控制在O(n)。
如果每次排序做,然后遍历数组,会超时。所以使用优先队列(这里是大根堆),每次取出队头,取出之后再插入它的三分之一向上取整。
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.TreeSet;class Solution {public long maxKelements(int[] nums, int k) {PriorityQueue<Integer>priorityQueue=new PriorityQueue<>(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2-o1;}});for(int i=0;i< nums.length;i++){priorityQueue.offer(nums[i]);}long ans=0;while(k>0){int num=priorityQueue.poll();ans+=num;num=(int)Math.ceil((double)num/3);priorityQueue.offer(num);k--;}return ans;}
}
关于优先队列的一些小结:
方法:
-
-
boolean
add(E e)
将指定的元素插入到此优先级队列中。
void
clear()
从此优先级队列中删除所有元素。
Comparator<? super E>
comparator()
返回用于为了在这个队列中的元素,或比较
null
如果此队列根据所述排序natural ordering的元素。boolean
contains(Object o)
如果此队列包含指定的元素,则返回
true
。Iterator<E>
iterator()
返回此队列中的元素的迭代器。
boolean
offer(E e)
将指定的元素插入到此优先级队列中。
E
peek()
检索但不删除此队列的头,如果此队列为空,则返回
null
。E
poll()
检索并删除此队列的头,如果此队列为空,则返回
null
。boolean
remove(Object o)
从该队列中删除指定元素的单个实例(如果存在)。
int
size()
返回此集合中的元素数。
Spliterator<E>
spliterator()
在此队列中的元素上创建late-binding和失败快速
Spliterator
。Object[]
toArray()
返回一个包含此队列中所有元素的数组。
<T> T[]
toArray(T[] a)
返回一个包含此队列中所有元素的数组; 返回的数组的运行时类型是指定数组的运行时类型。
-
优先队列默认小根(顶)堆。元素单调递增。
如果要自定义排序,需要重写Compare方法。
大根堆:
PriorityQueue<Integer>priorityQueue=new PriorityQueue<>(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2-o1;}
});
更多推荐
优先队列排序(JAVA)
发布评论